Subdomain Visit Count

Published: Sep 24, 2022

Medium Counting String Hash Table


As the title shows, this is a counting problem. The hash table is a good data structure to save subdomain name and count pairs. While counting, the given domain name should be divided first, then concatenate next in reverse order. How to concatenate might need a bit of consideration.

Problem Description

A website domain "" consists of various subdomains. At the top level, we have "com", at the next level, we have "" and at the lowest level, "". When we visit a domain like "", we will also visit the parent domains "" 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" is a count-paired domain that indicates that 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.


  • 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.
  • rep[i] is an integer in the range [1, 104].
  • d1[i], d2[i], and d3[i] consist of lowercase English letters.


Example 1
Input: cpdomains = ["9001"]
Output: ["9001","9001","9001 com"]
Example 2
Input: cpdomains = ["900", "50", "1", "5"]
Output: ["901","50","900","5","5 org","1","951 com"]


Each string should be divided by a space, then dot. The subdomain fragments will be concatenated in reverse order: com,, Add count in all of concatenated subdomains. Finally, hash table key-value pairs should be converted to strings.


class SubdomainVisitCount:
    def subdomainVisits(self, cpdomains: List[str]) -> List[str]:
        domains = collections.defaultdict(int)
        for cpdomain in cpdomains:
            cnt, domain = cpdomain.split(' ')
            cnt = int(cnt)
            names = domain.split('.')
            ns = names[-1]
            for i in range(len(names) - 2, -1, -1):
                domains[ns] += cnt
                ns = '.'.join([names[i], ns])
            domains[ns] += cnt
        return ['%s %s' % (v, k) for k, v in domains.items()]


  • Time: O(n)
  • Space: O(n)