GeeksforGeeks Hard

Number of Distinct Substrings

Count the distinct substrings of a string (the empty substring excluded).

triestringsuffix

02

Intuition

Generating all n²/2 substrings and dropping them into a set works but costs O(n³) time once the string copying is counted. The reframing that fixes it: every substring is a prefix of some suffix. So insert all n suffixes into a trie, and each node below the root corresponds to exactly one distinct substring — the path from the root spells it out. Duplicates collapse onto shared paths automatically, so the answer is simply the node count, with no explicit de-duplication anywhere.

How to spot this pattern

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.

03

Approach

1

Every substring is a prefix of a suffix

Take any substring s[i..j]; it is a prefix of the suffix starting at i. So the set of all substrings equals the set of all prefixes of all suffixes.

2

Insert every suffix into a trie

For each start index, walk the suffix, creating nodes only where the path does not already exist.

3

Count nodes, not insertions

Each non-root node is one distinct substring. Repeated substrings reuse existing nodes and therefore add nothing.

04

Solution & live demo

▶1class Solution:
▶2    def countDistinctSubstrings(self, s):
▶3        root = {}
▶4        count = 0
▶5        for i in range(len(s)):
▶6            node = root
▶7            for ch in s[i:]:
▶8                if ch not in node:
▶9                    node[ch] = {}
▶10                    count += 1              # a substring never seen before
▶11                node = node[ch]
▶12        return count

05

Common pitfalls

Generating substrings into a set

✗ Wrong

return len({s[i:j] for i in range(n) for j in range(i+1, n+1)})

✓ Right

for i in range(len(s)):
    node = root
    for ch in s[i:]:
        if ch not in node:
            node[ch] = {}; count += 1

Correct 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

✗ Wrong

node = node[ch]
count += 1

✓ Right

if ch not in node:
    node[ch] = {}
    count += 1

Walking 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

✗ Wrong

for i in range(len(s)):
    root[s[i:]] = True

✓ Right

for 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.

06

Edge cases

All characters identical, e.g. "aaa"

Only n substrings exist ("a", "aa", "aaa") — the trie is one straight path of n nodes.

All characters distinct

Nothing merges, so the count reaches the maximum n(n+1)/2.

Empty substring

Excluded by construction, since the root is not counted.

07

Complexity

Time

O(n²)

Space

O(n²)

n suffixes of length up to n. A suffix automaton reaches O(n), but the trie makes the 'prefix of a suffix' argument visible.