Subdomain Visit Count

medium hashing strings counting

Problem

Given count-paired domains like "9001 discuss.leetcode.com", return the visit count for each subdomain in any order, formatted as "count domain".

Inputcpdomains = ["9001 discuss.leetcode.com"]

Output["9001 discuss.leetcode.com","9001 leetcode.com","9001 com"]

Each parent subdomain inherits the same 9001 visits.

cpdomains

from collections import defaultdict

def subdomainVisits(cpdomains):
    cnt = defaultdict(int)
    for cp in cpdomains:
        c, dom = cp.split(' ')
        c = int(c)
        parts = dom.split('.')
        for i in range(len(parts)):
            cnt['.'.join(parts[i:])] += c
    return [f"{v} {k}" for k, v in cnt.items()]

var subdomainVisits = function(cpdomains) {
    const cnt = new Map();
    for (const cp of cpdomains) {
        const [c, dom] = cp.split(' ');
        const k = parseInt(c, 10);
        const parts = dom.split('.');
        for (let i = 0; i < parts.length; i++) {
            const sub = parts.slice(i).join('.');
            cnt.set(sub, (cnt.get(sub) || 0) + k);
        }
    }
    return Array.from(cnt, ([k, v]) => `${v} ${k}`);
};

class Solution {
    public java.util.List<String> subdomainVisits(String[] cpdomains) {
        java.util.Map<String, Integer> cnt = new java.util.HashMap<>();
        for (String cp : cpdomains) {
            String[] sp = cp.split(" ");
            int c = Integer.parseInt(sp[0]);
            String dom = sp[1];
            int idx = 0;
            while (true) {
                String sub = dom.substring(idx);
                cnt.merge(sub, c, Integer::sum);
                int dot = dom.indexOf('.', idx);
                if (dot == -1) break;
                idx = dot + 1;
            }
        }
        java.util.List<String> out = new java.util.ArrayList<>();
        for (var e : cnt.entrySet()) out.add(e.getValue() + " " + e.getKey());
        return out;
    }
}

class Solution {
public:
    vector<string> subdomainVisits(vector<string>& cpdomains) {
        unordered_map<string, int> cnt;
        for (auto& cp : cpdomains) {
            int sp = cp.find(' ');
            int c = stoi(cp.substr(0, sp));
            string dom = cp.substr(sp + 1);
            for (size_t i = 0; i != string::npos; ) {
                cnt[dom.substr(i)] += c;
                size_t dot = dom.find('.', i);
                if (dot == string::npos) break;
                i = dot + 1;
            }
        }
        vector<string> out;
        for (auto& [k, v] : cnt) out.push_back(to_string(v) + " " + k);
        return out;
    }
};

Explanation

A visit to discuss.leetcode.com also counts as a visit to its parent domains leetcode.com and com. So the plan is to take each entry, peel the domain into all its suffix subdomains, and add the visit count to each one in a hash map.

For each input like "9001 discuss.leetcode.com", we split off the number c and the domain. We split the domain on dots into parts.

Then for every starting index i, the suffix parts[i:] joined by dots is one subdomain, and we do cnt[suffix] += c. This walks from the full domain down to the top-level piece, giving each level the same c visits.

After all entries are processed, we turn the map into the "count domain" strings the problem asks for. Because it is a map, repeated subdomains across different inputs accumulate correctly.

Example: "9001 discuss.leetcode.com" adds 9001 to discuss.leetcode.com, leetcode.com, and com, producing those three count strings.

Time: O(N * L) Space: O(N * L)