Number of distinct substrings in a string
MediumInsert every suffix; count the nodes
Problem
Count the number of distinct substrings of a string (including the empty string or not, per definition).
Insert every suffix into a trie; each new branch created is one more distinct substring.
The idea
Every substring is a prefix of some suffix, so inserting all n suffixes into a trie makes each distinct substring exactly one node. Counting the nodes created therefore counts the distinct substrings, with duplicates collapsing automatically because they share a path.
The trick
- Number of distinct substrings = number of nodes created (plus one for the empty string, if counted).
- Building it is O(n²) nodes — fine up to a few thousand characters, use a suffix automaton beyond that.
This one walks through the worked example rather than tracing the algorithm frame by frame — a full walkthrough is still to be drawn. The code and the idea below are the real solution.
Step 1 of 2. Here's the example — ababa Values: 0.
1build a trie of all suffixes2count = number of nodes created (+1 for empty)3return countInput
- array
- [0]
Output
- answer
- —
Check yourself
3 quick questions about this walkthrough. A wrong answer costs nothing.
Examples
Example 1
- Input:
- s = "ababa"
- Output:
- 9
- Explanation:
- 9 unique substrings.
Example 2
- Input:
- s = "abc"
- Output:
- 6
- Explanation:
- 6 distinct substrings.
Example 3
- Input:
- s = "aaa"
- Output:
- 3
- Explanation:
- "a","aa","aaa" → 3.
Practice this problem:LeetCode (premium)(opens in a new tab)Search GeeksforGeeks(opens in a new tab)
Finished the walkthrough? Add it to your streak.