#811

Medium

auto_awesomeArray scanning plus hash lookup

LeetCode Problem Workspace

Subdomain Visit Count

The Subdomain Visit Count problem requires counting the visits to all subdomains of a given domain from a list of count-paired domains.

array hash table string counting

Problem Statement

Given a list of count-paired domains, where each entry consists of a visit count and a domain name, your task is to count the visits for every subdomain. For example, visiting 'discuss.leetcode.com' means visits to both 'leetcode.com' and 'com' are implicitly counted.

Each domain has a format where the number of visits is followed by a domain. Your goal is to return an array of subdomains, with their corresponding visit counts, considering all the subdomains in the hierarchy for each domain in the input.

Examples

Example 1

Input: cpdomains = ["9001 discuss.leetcode.com"]

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

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"]

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.

Solution Approach

Parse Input and Split Domains

To solve this problem, first split the input by spaces to separate the visit count from the domain. Then, break down the domain into its subdomains by iterating from the full domain down to its top-level components (e.g., 'discuss.leetcode.com' to 'com').

Count Visits Using a Hash Map

Use a hash map (dictionary) to store the visit counts for each subdomain. As you parse each domain and its subdomains, update the corresponding counts in the map. Be sure to accumulate visits for all levels of the domain hierarchy.

Return the Result

Finally, generate the output by converting the visit counts from the hash map into the desired format (visit count followed by subdomain). The result can be returned in any order, as specified in the problem.

Complexity Analysis

Metric	Value
Time	O(n \cdot m)
Space	O(n \cdot m)

The time complexity of this solution is O(n * m), where n is the number of input domains and m is the maximum length of a domain string. The space complexity is also O(n * m) due to the storage required for the hash map that tracks subdomain visit counts.

What Interviewers Usually Probe

Look for efficient handling of both domain parsing and counting subdomains.
Ensure the candidate uses an appropriate data structure for counting subdomains (like a hash map).
Test the candidate's understanding of subdomain hierarchy and handling nested domains.

Common Pitfalls or Variants

Common pitfalls

Failing to account for all subdomains of a given domain, including its parent domains.
Incorrectly managing the subdomain hierarchy, leading to missing visit counts for certain subdomains.
Not handling cases where multiple domains share the same subdomain.

Follow-up variants

Consider handling cases with very large input sizes, ensuring the solution scales efficiently.
Test cases with varying domain levels (e.g., some domains with three parts, others with two).
Edge cases where a domain has no subdomains.

FAQ

What is the best approach to solve the Subdomain Visit Count problem?

The most efficient approach involves using array scanning to break down each domain into its subdomains and counting visits with a hash map.

How do I handle domains with different levels of subdomains?

Ensure that you account for all subdomains from the most specific to the least specific, updating the visit counts for each parent domain.

What should I do if I encounter duplicate subdomains?

Accumulate the visit counts for duplicate subdomains using a hash map, ensuring the final count includes all visits from all occurrences.

Can I return the result in any order?

Yes, the problem statement allows returning the result in any order, as long as the visit counts for each subdomain are correct.

How does the Subdomain Visit Count problem relate to other string manipulation problems?

It requires breaking down and processing strings (domains), but with an added complexity of counting and handling nested structures through subdomains.

terminal

Solution

Solution 1

#### Python3

1

2

3

4

5

6

7

8

9

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 ' .':
                    cnt[s[i + 1 :]] += v
        return [f'{v} {s}' for s, v in cnt.items()]

Continue Practicing

#692 top k frequent words #1366 rank teams by votes #1684 count the number of consistent strings