DSA problem
Number of Distinct Substrings in a String
Given a string s, return the number of distinct non-empty substrings of s. Two substrings are considered the same if and only if they are equal as strings.
A brute-force solution generates every substring and inserts each into a hash set, taking O(n³) time because substring construction is O(n) and there are O(n²) substrings. For modest inputs this works, but the elegant interview answer is to use a trie of suffixes.
The key insight is that every substring of s is a prefix of some suffix of s. So if we insert all n suffixes of s into a trie, every distinct prefix in the trie corresponds to exactly one distinct substring. Counting the number of distinct prefixes is the same as counting how many new nodes the trie ever creates, because each new node represents a substring we have not seen before.
The algorithm therefore inserts suffixes one by one, and each time a character forces the creation of a brand-new trie node, we increment the answer. The total work is O(n²) since every suffix has length up to n, and the space is also O(n²) in the worst case. This is the standard interview-grade trie approach and runs comfortably within the constraints.
Examples
s = "aabbaba"21s = "abc"6s = "aaa"3Constraints
- 1 <= s.length <= 1000
- s consists of lowercase English letters.
3 hints and a full solution walkthrough with step-by-step visualizations are available in the practice editor.