A website domain "discuss.leetcode.com" consists of various subdomains. At the top level, we have "com", at the next level, we have "leetcode.com" and at the lowest level, "discuss.leetcode.com". When we visit a domain like "discuss.leetcode.com", we will also visit the parent domains "leetcode.com" 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.
"9001 discuss.leetcode.com" is a count-paired domain that indicates that discuss.leetcode.com 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.
Example 1:
Input: cpdomains = ["9001 discuss.leetcode.com"] Output: ["9001 leetcode.com","9001 discuss.leetcode.com","9001 com"] Explanation: 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"] Explanation: 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 <= 1001 <= cpdomain[i].length <= 100cpdomain[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.The key idea in #811 Subdomain Visit Count is that every domain contributes its visit count to all of its subdomains. For example, a domain like discuss.leetcode.com contributes to discuss.leetcode.com, leetcode.com, and com. The goal is to accumulate counts for each of these levels.
A practical approach is to use a hash table (or dictionary) to store the cumulative visit count for each subdomain. For every input entry, first parse the visit number and the full domain string. Then repeatedly extract subdomains by splitting the domain using . and building suffixes from right to left. Each generated subdomain is added to the map with the corresponding count.
Finally, convert the aggregated results into the required output format. This method leverages efficient string parsing and constant-time hash map updates. If there are n domain entries and each domain has at most k parts, the overall complexity remains efficient.
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| Hash Map with Subdomain Parsing | O(n * k) | O(m) |
Pepcoding
We will use a hashmap (or dictionary) to record the visit count of each subdomain as we process each count-paired domain in the input list. By splitting each domain into its subdomains, starting from the rightmost part, we accumulate the visits to each subdomain in the map.
Time Complexity: O(n * m) where n is the number of domains and m is the average number of subcomponents of a domain. Space Complexity: O(n * m) for storing subdomains in the map.
1def subdomainVisits(cpdomains):
2 counts = {}
3 for cpdomain in cpdomains:
4 count, domain = cpdomain.split()
5 count =
The Python implementation in `subdomainVisits` splits each domain into its subdomains and updates a dictionary with the counts for each subdomain. The result is constructed out of this dictionary.
We can also implement the solution using a trie structure to track domains. Each subcomponent of a domain traverses down nodes in the trie, updating the count at each node. This approach leverages the natural hierarchy of domains efficiently through a tree structure.
Time Complexity: O(n * m), n domains and m depth. Space Complexity: Higher space use due to node allocations.
1
Watch expert explanations and walkthroughs
Practice problems asked by these companies to ace your technical interviews.
Explore More ProblemsJot down your thoughts, approach, and key learnings
Yes, similar string parsing and hash map aggregation problems appear in FAANG-style interviews. This problem tests your ability to manipulate strings, handle hierarchical data, and efficiently count frequencies.
A hash table (dictionary) is the best data structure because it allows constant-time updates and lookups for each subdomain. This makes it efficient to aggregate counts as you parse each domain string.
The optimal approach uses a hash map to accumulate visit counts for each subdomain. For every domain entry, split the domain into its components and generate all suffix subdomains while adding the visit count to the map.
Each visit to a full domain implicitly counts as a visit to its parent subdomains. Generating all suffix subdomains ensures that the visit count is properly distributed across every level of the domain hierarchy.
Similar to Java, Python's Trie insertion and depth-first search traverses and links domain parts into nodes to form valid subdomains and results after parsing input strings aptly.