Trie Distinct Substrings

Description

How many distinct substrings does a string have? "banana" has 21 substring positions but only 15 distinct substrings. Generating every substring and hashing it works but builds O(n^2) strings of average length n/3 - O(n^3) characters. A trie shares the common parts.

This skill covers the suffix trie: insert every suffix, and count each newly created node as one new distinct substring. It also covers what that costs, which is O(n^2) nodes, and the linear-size structures that replace it on long strings.

We'll go from simple to more technical:

1. The pattern: insert all suffixes, counting new nodes.
2. A second flavor: what it costs, and when it stops being usable.
3. Where suffix structures run (full-text indexes, genomics, compression).
4. What breaks it: counting steps instead of nodes, materializing substrings, scale, the empty string.

The approach

int countDistinctSubstrings(String s) {
    TrieNode root = new TrieNode();
    int count = 0;
    for (int i = 0; i < s.length(); i++) {        // insert every suffix s[i..]
        TrieNode node = root;
        for (int j = i; j < s.length(); j++) {
            int c = s.charAt(j) - 'a';
            if (node.next[c] == null) {
                node.next[c] = new TrieNode();
                count++;                           // a new node = a substring not seen before
            }
            node = node.next[c];
        }
    }
    return count;
}

def count_distinct_substrings(s: str) -> int:
    root = TrieNode()
    count = 0
    for i in range(len(s)):                        # insert every suffix s[i:]
        node = root
        for c in s[i:]:
            if c not in node.next:
                node.next[c] = TrieNode()
                count += 1                         # a new node = a substring not seen before
            node = node.next[c]
    return count

Every substring is a prefix of some suffix, so inserting all suffixes puts every substring on some path - and each distinct substring on exactly one node. A substring that appears several times reuses its node, which is why counting only new nodes counts each distinct substring once. "aaaa" has 10 substring positions but only 4 distinct substrings (a, aa, aaa, aaaa).

A second flavor: what it costs

The suffix trie is O(n^2) in time and in nodes. For a random 1,000-letter string it builds about 499,000 nodes, each with its own 26-slot array - tens of megabytes. That's fine for n = 1,000 in a 256 MB sandbox - in Python, where every node is a full object with a dict of children, it's about 140 MB, still inside the limit - but the approach doesn't scale: n = 100,000 would need about 5 billion nodes. The HashSet<String> version is worse still - the 499,000 distinct substrings average about 330 characters, some 160 MB of string data.

Linear-size structures exist for exactly this reason. A suffix array (all suffixes sorted) plus the LCP array counts distinct substrings as n(n + 1)/2 - sum(LCP) in O(n log n); a suffix automaton does it in O(n).

Where you'll see it

Full-text search indexes and genome analysis use the compact descendants of the suffix trie - suffix arrays (with LCP arrays) and FM-indexes - to answer "does this pattern occur, and how often?" in time proportional to the pattern. Compression tools use related structures to find repeated substrings.

Which tool for which job?

Common mistakes

Check yourself

Try to answer before opening each one - recalling beats re-reading.

1. Why does inserting all suffixes put every substring into the trie?

2. Why count only newly created nodes?

3. Why doesn't this approach scale to strings of 10^5 characters?

Key takeaways

• Every substring is a prefix of a suffix: insert all suffixes.
• Count new nodes only - one per distinct substring.
• O(n^2) nodes: about 499,000 for 1,000 random letters.
• Large inputs need suffix arrays (+ LCP) or suffix automata.