Hard · Suffix Trie
Understand → Visualise → Practice.
Return the number of distinct non-empty substrings of text.
Insert every suffix into a trie. Each node corresponds to one distinct substring (the path from the root), so the answer is the number of nodes created.
For each start index, walk the suffix text[i:] into the trie.
Each time you create a node, you have found a substring not seen before.
The root (empty string) is not counted.
O(n²) time and O(n²) space for the trie; a suffix automaton does it in O(n).
Collecting substrings into a hash set also works but stores every substring separately, O(n³) characters.
Read the full guide first: Tries and Prefix Search.
Guest mode lets you understand, visualise and run the sample tests. Create a free account to submit and save your solutions.