Count Distinct Substrings — Suffix Trie Node Counting

Problem Statement#

Count Distinct Substrings of a String | Difficulty: Medium

Given a string s, return the number of distinct non-empty substrings of s.

Example:

Input:  s = "abc"
Output: 6
Explanation: distinct substrings are "a", "b", "c", "ab", "bc", "abc" → 6.
 
Input:  s = "aaa"
Output: 3
Explanation: distinct substrings are "a", "aa", "aaa" → 3.
 
Input:  s = "abab"
Output: 7
Explanation: "a","b","ab","ba","aba","bab","abab" → 7.

Constraints:

• 1 <= s.length <= 1000 for the suffix-trie solution. Larger inputs require suffix automaton or suffix array (advanced).
• Lowercase English letters.

Why This Problem Matters#

Counting distinct substrings is the entry point to suffix structures — suffix tries, suffix arrays, suffix automatons — which sit at the heart of bioinformatics, plagiarism detection, full-text search, and competitive programming. The problem appears on FAANG screens (Google, Amazon, Bloomberg) and Codeforces rounds because it elegantly demonstrates the "every substring is a prefix of a suffix" identity that unlocks an entire family of string algorithms.

The suffix trie solution is also the bridge to understanding the suffix automaton (Ukkonen's online construction), which counts distinct substrings in O(N) — a remarkable improvement that becomes essential for inputs longer than a few thousand characters.

The Core Insight#

Identity: Every substring of s is a prefix of some suffix of s.

Why? Take substring s[i..j]. The suffix starting at index i is s[i..n-1]. Its first j-i+1 characters form exactly s[i..j] — a prefix of that suffix. So the set of distinct substrings = the set of distinct prefixes across all suffixes.

Construction: Insert all n suffixes into a trie. After insertion, count the number of internal trie nodes (excluding the root). Each node represents exactly one distinct non-empty prefix-of-some-suffix → one distinct substring.

Counting trick: Increment a global counter every time a new node is created during insertion. After all suffixes are inserted, the counter equals the number of distinct substrings.

For s = "abc", suffixes are "abc", "bc", "c". Inserting them creates 6 new nodes — exactly matching the expected output.

Visual Dry Run#

s = "abab". Suffixes: "abab", "bab", "ab", "b".

Insert in order:

After "abab":         After "bab":          After "ab":          After "b":
   root                  root                  root                 root
    |-- a (1)             |-- a (1)             |-- a (1)            |-- a (1)
        |-- b (2)             |-- b (2)             |-- b (2)            |-- b (2)
            |-- a (3)             |-- a (3)             |-- a (3)            |-- a (3)
                |-- b (4)             |-- b (4)             |-- b (4)            |-- b (4)
                    |-- b (5)             |-- b (5)            |-- b (5)
                        |-- a (6)             |-- a (6)            |-- a (6)
                            |-- b (7)             |-- b (7)            |-- b (7)

After all four suffixes: 7 new nodes created → 7 distinct substrings.

Verification: "a", "b", "ab", "ba", "aba", "bab", "abab" — exactly 7.

Solution (Optimal) — Suffix Trie#

Python#

class TrieNode:
    __slots__ = ("children",)
    def __init__(self):
        self.children = {}
 
class Solution:
    def countDistinctSubstrings(self, s: str) -> int:
        root = TrieNode()
        count = 0
        n = len(s)
        for i in range(n):
            node = root
            for ch in s[i:]:
                if ch not in node.children:
                    node.children[ch] = TrieNode()
                    count += 1   # count fresh nodes only
                node = node.children[ch]
        return count

JavaScript#

class TrieNode {
  constructor() { this.children = {}; }
}
 
var countDistinctSubstrings = function(s) {
  const root = new TrieNode();
  let count = 0;
  const n = s.length;
  for (let i = 0; i < n; i++) {
    let node = root;
    for (let j = i; j < n; j++) {
      const ch = s[j];
      if (!node.children[ch]) {
        node.children[ch] = new TrieNode();
        count++;
      }
      node = node.children[ch];
    }
  }
  return count;
};

Alternative: Set of All Substrings (O(N^3) Time)#

def countDistinctSubstrings(s: str) -> int:
    return len({s[i:j] for i in range(len(s)) for j in range(i + 1, len(s) + 1)})

Concise but slower in practice — Python substring slicing is O(len) per slice, total O(N^3). Use the trie for n > 100.

Complexity#

• Time: O(N^2) — N suffixes, each up to length N, each character processed once.
• Space: O(N^2) in the worst case (string of all distinct characters).
• Suffix automaton (advanced): O(N) time and space — the canonical optimal solution for very large inputs.

Common Mistakes#

1. Counting only terminal nodes — terminals correspond to whole suffixes, not all substrings. Count every new node.
2. Including the root in the count — root represents the empty substring; the problem asks for non-empty substrings.
3. Inserting only the full string — would count distinct prefixes of s, not distinct substrings of s.
4. Forgetting to break out of the inner loop's "char already exists" — there is no break needed; if the char exists you simply walk into it without incrementing the counter.
5. Confusing this with "longest distinct substring" — different problem (sliding window territory).
6. Trying to use a hash set on N > 10^4 — O(N^3) substring construction will TLE; switch to suffix automaton.

Interview Tips#

• State the identity upfront: "Every substring is a prefix of some suffix."
• Pitch the construction: "Insert all suffixes into a trie; count nodes; that is the answer."
• Justify the counting rule: "Increment only when we create a new node — duplicates do not contribute."
• Mention the brute force set solution to show you considered the simple option.
• For inputs > 1000, mention suffix automaton (O(N)) as the production-grade alternative; you do not need to implement it on the whiteboard.
• Note that this primitive — "count distinct prefixes-of-suffixes" — also gives you the longest repeated substring and the longest common substring as byproducts.

Follow-up Questions#

• Find the longest distinct substring (no repeats inside)? Different problem — sliding window, not suffix trie.
• Count distinct substrings of length exactly k? Sliding window of size k + hash set, or BFS suffix trie at depth k.
• Lexicographically k-th distinct substring? Suffix array + LCP array, or DFS the suffix trie counting subtree sizes.
• Counting distinct substrings of two strings (common to both)? Generalised suffix tree.
• Online (string grows)? Ukkonen's suffix automaton handles online inserts in amortised O(1) per character.

Key Takeaways#

• Every substring is a prefix of some suffix — the foundational identity behind suffix data structures.
• Insert every suffix into a trie; count newly created nodes; that count equals distinct substring count.
• Time and space are O(N^2) for the suffix trie; suitable for N up to ~1000.
• Suffix automaton achieves O(N) time and space and is the production solution for large strings.
• Watch for off-by-one: do not count the root, do count every new internal node.
• This primitive unlocks longest repeated substring, longest common substring, lexicographic substring rank, and full-text search indexing.