Number of Distinct Substrings
Count the distinct substrings of a string (the empty substring excluded).
- 1 <= |s| <= 10³
- s consists of lowercase English letters
- The empty substring is not counted
Intuition
Number of distinct substrings counts how many different substrings a string has, excluding the empty one. Generating all of them and putting them in a set is correct but costs O(n³) once the copying of each substring is counted, since there are about n²/2 substrings averaging n/2 characters each.
The reframing that fixes it is a small observation with a large consequence:
- Every substring is a prefix of some suffix — the substring s[i..j] is a prefix of the suffix starting at i.
So the set of all substrings is exactly the set of all prefixes of all suffixes. And a trie is precisely the structure whose nodes are prefixes.
Insert all n suffixes into a trie. Each node below the root corresponds to one distinct substring, spelled out by the path from the root to it. Duplicate substrings arrive along paths that already exist, so they create no new nodes — the de-duplication happens structurally, with no set and no comparison anywhere.
The answer is therefore just the node count, excluding the root.
Worth being honest about the cost: this is O(n²) in both time and space, since the total length of all suffixes is n(n+1)/2. That is a real improvement over the naive O(n³), but for very long strings a suffix automaton achieves O(n), which is the direction to mention if asked to go further.
Every substring is a prefix of some suffix — so inserting all suffixes into a trie and counting the new nodes created counts distinct substrings exactly. Each node corresponds to one unique substring, and the trie collapses shared prefixes automatically. Reframing "substrings" as "prefixes of suffixes" is the whole unlock.
Approach
Before reading on: price up what enumerating every case costs here, then ask what the shared prefixes let you avoid storing twice. Aim for O(n²) time and O(n²) space.
See substrings as prefixes of suffixes
Any substring s[i..j] is a prefix of the suffix beginning at i. This equivalence is the entire idea — it converts an unstructured collection into something a trie indexes naturally.
Insert every suffix into a trie
For each start index, walk the suffix from the root, creating nodes only where the path does not already exist. Repeated substrings follow existing paths and add nothing.
Count nodes rather than insertions
Each non-root node represents exactly one distinct substring. No end-of-word flags and no de-duplication step are needed — the trie's structure enforces uniqueness by construction.
Increment as nodes are created
Keep a running counter incremented each time a new node is allocated. Traversing the finished trie to count also works, but counting during insertion avoids a second pass.
Exclude the root
The root corresponds to the empty substring, which the problem excludes. Counting only created nodes handles this automatically, since the root is never created during an insertion.
Cost and the better alternative
The suffixes total n(n+1)/2 characters, so this is O(n²) time and space — a solid gain over the naive O(n³). For very long strings, a suffix automaton counts distinct substrings in O(n), which is the answer to a follow-up asking for better.
Solution & live demo
Common pitfalls
Generating substrings into a set
return len({s[i:j] for i in range(n) for j in range(i+1, n+1)})for i in range(len(s)):
node = root
for ch in s[i:]:
if ch not in node:
node[ch] = {}; count += 1Correct but stores O(n²) substrings of average length O(n) — O(n³) memory. The trie shares prefixes, so equal substrings occupy the same nodes and are never duplicated.
Counting nodes visited rather than nodes created
node = node[ch] count += 1
if ch not in node:
node[ch] = {}
count += 1Walking an existing path means that substring was already counted from an earlier suffix. Only a newly created node represents a substring never seen before.
Inserting only whole suffixes without walking each character
for i in range(len(s)):
root[s[i:]] = Truefor ch in s[i:]:
...That stores n suffixes as opaque keys and counts n, not the number of distinct substrings. The character-by-character descent is what makes every prefix of every suffix its own node.
Edge cases
Only n substrings exist ("a", "aa", "aaa") — the trie is one straight path of n nodes.
Nothing merges, so the count reaches the maximum n(n+1)/2.
Excluded by construction, since the root is not counted.