We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Subdomain Visit Count

Number: 829

Difficulty: Medium

Paid? No

Companies: Roblox, Wix

Problem Description

Given a list of count-paired domains, each in the format "rep domain" (for example, "9001 discuss.leetcode.com"), count the number of visits for every subdomain. When a domain is visited, all of its parent domains are implicitly visited as well. The goal is to aggregate the visit counts for each subdomain and return the results in any order.

Key Insights

  • A single domain visit (like "discuss.leetcode.com") implies visits to all its subdomains ("leetcode.com" and "com").
  • By splitting the input string, extract both the count and the domain.
  • Use string splitting (by ".") to obtain all possible subdomains.
  • Utilize a hash table (or map) to accumulate counts for each subdomain efficiently.
  • Finally, format the aggregated counts back into the required "count domain" string format.

Space and Time Complexity

Time Complexity: O(N * L) where N is the number of count-paired domains and L is the average number of subdomain levels per domain.
Space Complexity: O(M) where M is the number of unique subdomains stored in the hash table.

Solution

The solution leverages a hash table (or equivalent) to map each subdomain to its total visit count. For each count-paired domain:

  1. Split the string into the count and the domain.
  2. Split the domain by '.' to generate all subdomains.
  3. For each subdomain (from most specific to least specific), update the hash table with the accumulated count.
  4. After processing all inputs, convert the hash table entries into the required output format ("count domain").

This method is efficient due to the limited size of the input and is straightforward in logic.

Code Solutions

# Define a function to count subdomain visits.
def subdomain_visits(cpdomains):
    # Dictionary to hold subdomain counts.
    subdomain_counts = {}
    
    # Iterate over each count-paired domain.
    for cp in cpdomains:
        # Split into count and domain.
        count_str, domain = cp.split(" ")
        count = int(count_str)
        # Split the domain into parts by '.'
        fragments = domain.split(".")
        # Generate each subdomain by joining fragments from various starting points.
        for i in range(len(fragments)):
            subdomain = ".".join(fragments[i:])
            subdomain_counts[subdomain] = subdomain_counts.get(subdomain, 0) + count
    
    # Format results as a list of "count domain" strings.
    return [str(cnt) + " " + subdomain for subdomain, cnt in subdomain_counts.items()]

# Example usage:
cpdomains = ["9001 discuss.leetcode.com"]
result = subdomain_visits(cpdomains)
print(result)
← Back to All Questions