# Subdomain Visit Count
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/subdomain-visit-count)
Canonical: https://scaleengineer.com/dsa/problems/subdomain-visit-count
**Patterns:** [Counting](https://scaleengineer.com/dsa/patterns/counting)
**Data structures:** Array, Hash Table, String
**Companies:** [Karat](https://scaleengineer.com/companies/karat), [Roblox](https://scaleengineer.com/companies/roblox), [Wix](https://scaleengineer.com/companies/wix), [Peloton](https://scaleengineer.com/companies/peloton)
---
## Problem
A website domain `"discuss.leetcode.com"` consists of various subdomains. At the top level, we have `"com"`, at the next level, we have `"leetcode.com"` and at the lowest level, `"discuss.leetcode.com"`. When we visit a domain like `"discuss.leetcode.com"`, we will also visit the parent domains `"leetcode.com"` and `"com"` implicitly.

A **count-paired domain** is a domain that has one of the two formats `"rep d1.d2.d3"` or `"rep d1.d2"` where `rep` is the number of visits to the domain and `d1.d2.d3` is the domain itself.

* For example, `"9001 discuss.leetcode.com"` is a **count-paired domain** that indicates that `discuss.leetcode.com` was visited `9001` times.

Given an array of **count-paired domains** `cpdomains`, return _an array of the **count-paired domains** of each subdomain in the input_. You may return the answer in **any order**.

**Example 1:**

**Input:** cpdomains = ["9001 discuss.leetcode.com"]
**Output:** ["9001 leetcode.com","9001 discuss.leetcode.com","9001 com"]
**Explanation:** We only have one website domain: "discuss.leetcode.com".
As discussed above, the subdomain "leetcode.com" and "com" will also be visited. So they will all be visited 9001 times.

**Example 2:**

**Input:** cpdomains = ["900 google.mail.com", "50 yahoo.com", "1 intel.mail.com", "5 wiki.org"]
**Output:** ["901 mail.com","50 yahoo.com","900 google.mail.com","5 wiki.org","5 org","1 intel.mail.com","951 com"]
**Explanation:** We will visit "google.mail.com" 900 times, "yahoo.com" 50 times, "intel.mail.com" once and "wiki.org" 5 times.
For the subdomains, we will visit "mail.com" 900 + 1 = 901 times, "com" 900 + 50 + 1 = 951 times, and "org" 5 times.

**Constraints:**

* `1 <= cpdomain.length <= 100`
* `1 <= cpdomain[i].length <= 100`
* `cpdomain[i]` follows either the `"repi d1i.d2i.d3i"` format or the `"repi d1i.d2i"` format.
* `repi` is an integer in the range `[1, 104]`.
* `d1i`, `d2i`, and `d3i` consist of lowercase English letters.

# Approaches
## Brute Force with Intermediate List
This approach first processes each input string to generate all possible subdomains along with their visit counts. These (count, subdomain) pairs are stored in an intermediate list. After generating all pairs from all input strings, we iterate through this list to aggregate the counts for each unique subdomain. This aggregation involves another nested loop, making it less efficient.
**Time:** O(S + N^2 * L), where N is the number of `cpdomains`, L is the maximum length of a domain, and S is the total number of characters in the input. Generating all pairs takes O(S). The aggregation step involves nested loops over a list of size O(N), with string comparisons of length O(L), resulting in O(N^2 * L) complexity. For the given constraints, this is dominated by the O(N^2 * L) term. · **Space:** O(S), where S is the total number of characters in the input array. This space is used to store the intermediate list of all subdomain pairs (`allPairs`) and the set of processed domains (`processedDomains`).
**Pros:** Conceptually simple, breaking the problem into two distinct phases: generation and aggregation.; Does not require knowledge of more complex data structures like hash maps.
**Cons:** Highly inefficient due to the nested loop for aggregation, leading to a quadratic time complexity relative to the number of input domains.; Uses significant intermediate storage for the list of all pairs before aggregation.
### Explanation
This method breaks the problem into two main phases: generation and aggregation. First, it generates a comprehensive list of every single subdomain visit. For example, `"900 google.mail.com"` would generate three entries in a list: `(900, "google.mail.com")`, `(900, "mail.com")`, and `(900, "com")`. After this list is populated with data from all input strings, a second phase begins. This phase calculates the total count for each unique domain by iterating through the generated list. For each domain, it performs another full scan of the list to sum up the counts, which is computationally expensive.

```java
import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.Set;

class Solution {
    public List<String> subdomainVisits(String[] cpdomains) {
        // A simple class to hold the pair
        class Pair {
            int count;
            String domain;
            Pair(int count, String domain) {
                this.count = count;
                this.domain = domain;
            }
        }

        List<Pair> allPairs = new ArrayList<>();
        for (String cpdomain : cpdomains) {
            String[] parts = cpdomain.split(" ");
            int count = Integer.parseInt(parts[0]);
            String domain = parts[1];

            while (true) {
                allPairs.add(new Pair(count, domain));
                int dotIndex = domain.indexOf('.');
                if (dotIndex == -1) {
                    break;
                }
                domain = domain.substring(dotIndex + 1);
            }
        }

        List<String> result = new ArrayList<>();
        Set<String> processedDomains = new HashSet<>();

        for (Pair p1 : allPairs) {
            if (processedDomains.contains(p1.domain)) {
                continue;
            }

            int totalCount = 0;
            for (Pair p2 : allPairs) {
                if (p1.domain.equals(p2.domain)) {
                    totalCount += p2.count;
                }
            }
            result.add(totalCount + " " + p1.domain);
            processedDomains.add(p1.domain);
        }

        return result;
    }
}
```
### Algorithm
- Create a helper class or structure to hold `(count, domain)` pairs.
- Initialize an empty list, `allPairs`, to store these pairs.
- Iterate through each `cpdomain` string in the input array:
  - Parse the string to get the initial `count` and the `fullDomain`.
  - Use a loop and string manipulation functions like `indexOf('.')` and `substring()` to find all subdomains (e.g., `discuss.leetcode.com`, `leetcode.com`, `com`).
  - For each generated subdomain, create a pair with the original count and add it to the `allPairs` list.
- Initialize an empty list for the final results, `resultList`, and a `Set` to track processed domains, `processedDomains`.
- Iterate through the `allPairs` list (outer loop).
  - For each pair, get its `domain`.
  - If the `domain` is in `processedDomains`, skip it.
  - If not, initialize `totalCount = 0`.
  - Start an inner loop, iterating through `allPairs` again.
  - If a pair in the inner loop has the same domain, add its count to `totalCount`.
  - After the inner loop finishes, add the formatted string `totalCount + " " + domain` to `resultList`.
  - Add the `domain` to `processedDomains` to avoid recounting.
- Return `resultList`.

## Efficient Approach using Hash Map
This is the optimal approach. It uses a hash map to store the visit counts for each subdomain. We iterate through the input array once. For each count-paired domain, we parse it, generate all its subdomains, and update their counts directly in the hash map. This avoids any repeated computations or nested loops for aggregation. Finally, we convert the map entries into the required output format.
**Time:** O(S), where S is the total number of characters in the `cpdomains` array. For each `cpdomain`, we iterate through it to parse and generate subdomains. Let N be the number of `cpdomains` and L be the average length of a domain. The complexity is O(N * L), which is equivalent to O(S). · **Space:** O(S), where S is the total number of characters in the `cpdomains` array. In the worst case, every generated subdomain is unique, and we would need to store all of them in the hash map. The total length of all subdomains is proportional to S.
**Pros:** Highly efficient with a linear time complexity relative to the total number of characters in the input.; Processes and aggregates counts in a single pass, avoiding redundant work.; The use of a hash map provides average O(1) time complexity for lookups and insertions (amortized, though string operations dominate), making the aggregation step very fast.
**Cons:** Requires extra space for the hash map, which can be proportional to the total size of the input if all subdomains are unique.
### Explanation
The core idea of this efficient approach is to use a hash map for on-the-fly aggregation. As we process each line from the input, we immediately update the counts for all associated subdomains. This eliminates the need for an intermediate list and a separate, costly aggregation step. The hash map provides (on average) constant-time access for retrieving and updating counts, making the entire process very fast.

For example, when processing `"900 google.mail.com"`, we update the counts for `"google.mail.com"`, `"mail.com"`, and `"com"` right away. When we later process `"1 intel.mail.com"`, we simply add `1` to the existing counts for `"mail.com"` and `"com"`.

```java
import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

class Solution {
    public List<String> subdomainVisits(String[] cpdomains) {
        Map<String, Integer> counts = new HashMap<>();

        for (String cpdomain : cpdomains) {
            String[] parts = cpdomain.split(" ");
            int count = Integer.parseInt(parts[0]);
            String domain = parts[1];

            while (true) {
                counts.put(domain, counts.getOrDefault(domain, 0) + count);
                int dotIndex = domain.indexOf('.');
                if (dotIndex == -1) {
                    break;
                }
                domain = domain.substring(dotIndex + 1);
            }
        }

        List<String> result = new ArrayList<>();
        for (Map.Entry<String, Integer> entry : counts.entrySet()) {
            result.add(entry.getValue() + " " + entry.getKey());
        }

        return result;
    }
}
```
### Algorithm
- Initialize a `HashMap<String, Integer>` called `counts` to store the visit count for each subdomain.
- Iterate through each string `cpdomain` in the input array `cpdomains`.
- For each `cpdomain`:
  - Parse the string to get the `count` and the full `domain`.
  - Use a `while` loop that continues as long as the `domain` string is valid.
  - In the loop, add the `count` to the current `domain`'s entry in the `counts` map. Use `map.getOrDefault(key, 0)` to handle domains seen for the first time.
  - Find the index of the first dot (`.`) in the current `domain`.
  - If a dot is found, update `domain` to be the substring after the dot (e.g., `discuss.leetcode.com` becomes `leetcode.com`).
  - If no dot is found, break the loop.
- After processing all `cpdomains`, initialize an empty `ArrayList<String>` for the results.
- Iterate through the key-value pairs in the `counts` map.
- For each pair `(domain, count)`, create the formatted string `count + " " + domain` and add it to the result list.
- Return the result list.

# Solutions
### Java

```java
class Solution { public List < String > subdomainVisits ( String [] cpdomains ) { Map < String , Integer > cnt = new HashMap <>(); for ( String s : cpdomains ) { int i = s . indexOf ( " " ); int v = Integer . parseInt ( s . substring ( 0 , i )); for (; i < s . length (); ++ i ) { if ( s . charAt ( i ) == ' ' || s . charAt ( i ) == '.' ) { String t = s . substring ( i + 1 ); cnt . put ( t , cnt . getOrDefault ( t , 0 ) + v ); } } } List < String > ans = new ArrayList <>(); for ( var e : cnt . entrySet ()) { ans . add ( e . getValue () + " " + e . getKey ()); } return ans ; } }
```

### CPP

```cpp
class Solution {
public:
  vector<string> subdomainVisits(vector<string> &cpdomains) {
    unordered_map<string, int> cnt;
    for (auto &s : cpdomains) {
      int i = s.find(' ');
      int v = stoi(s.substr(0, i));
      for (; i < s.size(); ++i) {
        if (s[i] == ' ' || s[i] == '.') {
          cnt[s.substr(i + 1)] += v;
        }
      }
    }
    vector<string> ans;
    for (auto &[s, v] : cnt) {
      ans.push_back(to_string(v) + " " + s);
    }
    return ans;
  }
};

```

### Python

```python
from collections import Counter class Solution : def subdomainVisits ( self , cpdomains : List [ str ]) -> List [ str ]: cnt = Counter () for s in cpdomains : v = int ( s [: s . index ( ' ' )]) for i , c in enumerate ( s ): if c in ' .' : # space ' ' is for the full domain, and '.' for subdomain cnt [ s [ i + 1 :]] += v return [ f ' { v } { s } ' for s , v in cnt . items ()] ############ class Solution ( object ): def subdomainVisits ( self , cpdomains ): """ :type cpdomains: List[str] :rtype: List[str] """ domain_counts = collections . defaultdict ( int ) for cpdomain in cpdomains : times , domains = cpdomain . split () times = int ( times ) domain_counts [ domains ] += times while '.' in domains : domains = domains [ domains . index ( '.' ) + 1 :] domain_counts [ domains ] += times return [ str ( v ) + ' ' + d for d , v in domain_counts . items ()]
```