Coding Interview PatternsNumber of Distinct Substrings in a String
HardTrie
Number of Distinct Substrings in a String
Explanation & Solution
Description
Given a string s, return the number of distinct non-empty substrings of s.
A substring is a contiguous sequence of characters within the string.
Input: s = "aabb"
Output: 8
Explanation: The 8 distinct substrings are: "a", "aa", "aab", "aabb", "ab", "abb", "b", "bb".
Constraints
1 <= s.length <= 500sconsists of lowercase English letters
Approach
Trie pattern
1. Use a Trie to Track Unique Substrings
- A trie naturally deduplicates prefixes — each unique path from root to a node represents a unique substring
- Every time we create a new node, it corresponds to a new distinct substring
2. Insert All Suffixes
- For each starting index
ifrom0ton-1, insert the suffixs[i..n-1]into the trie character by character - As we insert
s[i], s[i+1], ..., we traverse deeper into the trie
3. Count New Nodes
- When traversing for suffix starting at
i, if characters[j]does not exist as a child of the current node, create a new node and incrementcount - If the child already exists, we simply traverse into it (this substring was already seen from an earlier suffix)
4. Why This Works
- Every distinct substring of
sis a prefix of some suffix ofs - Inserting all suffixes into the trie means every prefix of every suffix is represented
- Each new trie node = one new distinct substring
5. Return the Count
- After inserting all suffixes,
countholds the total number of distinct non-empty substrings
Key Insight
- The trie acts as a compressed representation of all distinct substrings
- Time complexity is O(n^2) for inserting all suffixes, which is optimal for this approach
- Space complexity is O(n^2) in the worst case for the trie nodes (all substrings are distinct)
Visualization
Input:
[a, a, b, b]
—
No animation available
Left (L)Right (R)ConvergedDone
0 steps