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.

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

python

▶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

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.

06

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.