Subdomain Visit Count

Problem Statement

In web architecture, a website domain can have multiple subdomains attributed to it. For example, the domain support.vultrcloud.com includes the subdomains vultrcloud.com at a higher level and com at the top level. When a user visits the lowest-level domain, all its parent domains are considered visited.

To quantify visits, a count-paired domain notation is used, which pairs the number of visits with the domain in question in the format "rep d1.d2.d3". Here, rep denotes the number of visits, and d1.d2.d3 illustrates the domain hierarchy.

Given an input array containing these count-paired domains, your task is to compute and return an array that includes the visit count for every level of domain from the input. The results can be returned in any order.

Examples

Example 1

Input:

cpdomains = ["9001 support.vultrcloud.com"]

Output:

["9001 vultrcloud.com", "9001 support.vultrcloud.com", "9001 com"]

Explanation:

We only have one website domain: "support.vultrcloud.com".
As discussed above, the subdomains "vultrcloud.com" and "com" will also be visited.
So all three domains will be visited 9001 times.

Example 2

Input:

cpdomains = ["900 edge.hosting.net", "50 vultr.com", "1 login.hosting.net", "5 wiki.org"]

Output:

["901 hosting.net", "50 vultr.com", "900 edge.hosting.net", "5 wiki.org", "5 org", "1 login.hosting.net", "951 net"]

Explanation:

We will visit "edge.hosting.net" 900 times, "vultr.com" 50 times, "login.hosting.net" once, and "wiki.org" 5 times.

For subdomains:
- "hosting.net" gets 900 + 1 = 901 visits.
- "net" gets 900 + 1 = 901, but also add 50 if "vultr.com" is under ".net" (it is not, so "net" remains 901).
- "org" gets 5 visits.

Constraints

• 1 <= cpdomains.length <= 100
• 1 <= cpdomains[i].length <= 100
• cpdomains[i] follows the format "repi d1i.d2i.d3i" or "repi d1i.d2i"
• repi is an integer in the range [1, 10^4]
• d1i, d2i, and d3i consist of lowercase English letters only

Approach and Intuition

To solve this:

1. Parse Each Entry: Split each entry into count and domain.

2. Generate All Subdomains: For each domain like "a.b.c", generate:

   • "a.b.c"
   • "b.c"
   • "c"

3. Count Each Subdomain: Use a hashmap (dictionary) to accumulate visit counts for each subdomain.

4. Format Output: Convert the hashmap into a list of strings like "count subdomain".

This method is efficient for the given constraints. Time complexity is O(n * m), where n is the number of entries and m is the number of subdomain parts (typically ≤3).

Solutions

class Solution {
    public List<String> countSubdomainVisits(String[] cpdomains) {
        Map<String, Integer> visitCounts = new HashMap<>();
        for (String domain : cpdomains) {
            String[] parts = domain.split("\\s+");
            String[] subdomains = parts[1].split("\\.");
            int visitNumber = Integer.parseInt(parts[0]);
            String currentDomain = "";
            for (int i = subdomains.length - 1; i >= 0; i--) {
                currentDomain = subdomains[i] + (i < subdomains.length - 1 ? "." : "") + currentDomain;
                visitCounts.put(currentDomain, visitCounts.getOrDefault(currentDomain, 0) + visitNumber);
            }
        }

        List<String> results = new ArrayList<>();
        for (String domain : visitCounts.keySet()) {
            results.add(visitCounts.get(domain) + " " + domain);
        }
        return results;
    }
}