Problem statement

A domain such as api.codekairo.com is made of labels separated by dots. Visiting it also counts as a visit to each of its parent domains: codekairo.com and com.

Each entry of cpdomains is a count-paired domain "rep domain": the domain was visited rep times. Return the total number of visits for every domain or parent domain that appears, each as a string "total domain".

Return the strings sorted by domain, in ascending lexicographic order (plain character comparison).

Example 1

Input: cpdomains = ["900 api.codekairo.com","50 codekairo.com","7 mail.yahoo.com"]
Output: ["900 api.codekairo.com","950 codekairo.com","957 com","7 mail.yahoo.com","7 yahoo.com"]
Explanation: `com` collects 900 + 50 + 7.

Example 2

Input: cpdomains = ["3 a.io","4 b.a.io"]
Output: ["7 a.io","4 b.a.io","7 io"]

Constraints

• 1 <= cpdomains.length <= 100
• 1 <= cpdomains[i].length <= 100
• cpdomains[i] is "rep d1.d2.d3" or "rep d1.d2"
• 1 <= rep <= 10^4
• d1, d2 and d3 consist of lowercase English letters

Hints for Subdomain Visit Count

1. Hint 1

   Every suffix of a domain that starts right after a dot (and the domain itself) receives the visits.

2. Hint 2

   Accumulate the counts in a hash map keyed by domain.

3. Hint 3

   Sort the map's keys at the end and format each line as count + " " + domain.

How to solve Subdomain Visit Count

Each count-paired domain contributes its count to itself and to every dot-suffix of it; a hash map sums those contributions.

Approach

1. For each entry, split at the space into rep and domain.
2. Add rep to count[domain]; then repeatedly cut the domain after its first dot and add rep to the shorter domain, until there is no dot left.
3. Sort the domains in the map and emit "<count> <domain>" for each.

Why it works

The parent domains of d1.d2.d3 are exactly its suffixes d2.d3 and d3, each starting right after a dot, so cutting after the first dot repeatedly visits the domain and all its parents once. Summing in the map merges visits that reach the same domain from different entries.

Complexity

• Time — O(N · L + D log D) for N entries of length at most L and D distinct domains
• Space — O(D · L)

Pitfalls

• Counting the top-level label com but forgetting the full domain itself (or vice versa).
• Sorting the output strings instead of the domains puts "10 b.io" before "9 a.io".
• Parsing rep as part of the domain — split at the space first.

Reference solution

Python

from typing import List

def subdomainVisits(cpdomains: List[str]) -> List[str]:
    count = {}
    for cp in cpdomains:
        rep, dom = cp.split(" ")
        rep = int(rep)
        while True:
            count[dom] = count.get(dom, 0) + rep
            dot = dom.find(".")
            if dot < 0:
                break
            dom = dom[dot + 1:]
    return [str(count[d]) + " " + d for d in sorted(count)]

Java

public static String[] subdomainVisits(String[] cpdomains) {
    TreeMap<String, Integer> count = new TreeMap<>();
    for (String cp : cpdomains) {
        int sp = cp.indexOf(' ');
        int rep = Integer.parseInt(cp.substring(0, sp));
        String dom = cp.substring(sp + 1);
        while (true) {
            count.merge(dom, rep, Integer::sum);
            int dot = dom.indexOf('.');
            if (dot < 0) break;
            dom = dom.substring(dot + 1);
        }
    }
    String[] res = new String[count.size()];
    int k = 0;
    for (Map.Entry<String, Integer> e : count.entrySet()) res[k++] = e.getValue() + " " + e.getKey();
    return res;
}

C++

vector<string> subdomainVisits(vector<string>& cpdomains) {
    map<string, int> count;
    for (const string& cp : cpdomains) {
        size_t sp = cp.find(' ');
        int rep = stoi(cp.substr(0, sp));
        string dom = cp.substr(sp + 1);
        while (true) {
            count[dom] += rep;
            size_t dot = dom.find('.');
            if (dot == string::npos) break;
            dom = dom.substr(dot + 1);
        }
    }
    vector<string> res;
    for (auto& e : count) res.push_back(to_string(e.second) + " " + e.first);
    return res;
}

JavaScript

var subdomainVisits = function(cpdomains) {
    var count = new Map();
    for (var i = 0; i < cpdomains.length; i++) {
        var sp = cpdomains[i].indexOf(" ");
        var rep = parseInt(cpdomains[i].substring(0, sp), 10);
        var dom = cpdomains[i].substring(sp + 1);
        while (true) {
            count.set(dom, (count.has(dom) ? count.get(dom) : 0) + rep);
            var dot = dom.indexOf(".");
            if (dot < 0) break;
            dom = dom.substring(dot + 1);
        }
    }
    var keys = Array.from(count.keys()).sort();
    return keys.map(function(d) { return count.get(d) + " " + d; });
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

More arrays problems

• Implement Router Medium
• Design Memory Allocator Medium
• Design a Food Rating System Medium
• Design an ATM Machine Medium
• Design Bitset Medium
• Range Frequency Queries Medium