Count Distinct Substrings — Suffix Array, Suffix Automaton, and Rolling Hash

Problem and Topic Statement#

Count Distinct Substrings — given a string s of length n, return the number of distinct non-empty substrings of s.

Example: s = "aba" has substrings a, b, a, ab, ba, aba. Removing duplicates yields a, b, ab, ba, aba — five distinct substrings.

The problem looks innocent but the brute force is O(n^2) substring enumeration plus deduplication, which is O(n^3) worst case if you compare strings naively. Optimal solutions sit at O(n log n) using suffix arrays plus LCP, or O(n) using suffix automata. This problem is the gateway question that forces candidates to think structurally about all suffixes of a string at once.

Why This Topic Matters#

Counting distinct substrings is one of the canonical problems used to introduce suffix arrays, suffix trees, and suffix automata in competitive programming. It appears in Google interviews, Codeforces rounds, ICPC regionals, and Meta's harder onsite slots because it combines string algorithms, combinatorics, and data structure design.

The reason this matters in production is bigger than it seems. Suffix-data-structure techniques power genome alignment (BWA, Bowtie), full-text search indexes (FM-index, Lucene's term dictionary), data compression (BWT in bzip2, suffix-tree compression in LZ-family algorithms), and biological sequence search. Counting distinct substrings is the toy problem that exercises every primitive.

The technique transfer is enormous. Once you can count distinct substrings via a suffix array, you can also compute the longest common substring of two strings, the longest repeated substring, the lexicographically smallest cyclic rotation, and dozens of other classic problems with minor modifications.

The Core Insight#

Every substring of s is a prefix of some suffix of s. There are exactly n suffixes. The total number of (suffix, prefix) pairs is n*(n+1)/2, but many of these prefixes repeat across suffixes. Removing duplicates is the question.

Approach 1 — Hash set. Generate all O(n^2) substrings and store them in a hash set. Time O(n^2) on average if you use rolling hashing for O(1) substring comparison; O(n^3) worst case otherwise. Memory is O(n^2).

Approach 2 — Suffix array plus LCP array. Sort all suffixes lexicographically. The number of distinct substrings equals the total length of all suffixes minus the sum of LCPs between consecutive sorted suffixes:

distinct = sum(n - sa[i]) - sum(lcp[i])
        = n*(n+1)/2 - sum(lcp)

The intuition: each suffix of length L contributes L prefixes (which are substrings). When two consecutive sorted suffixes share a prefix of length lcp, those lcp prefixes are duplicates already counted by the earlier suffix. Subtract them.

Building the suffix array is O(n log n) with the doubling trick or O(n) with DC3 / SA-IS. Computing the LCP array from the suffix array via Kasai's algorithm is O(n).

Approach 3 — Suffix automaton (SAM). A suffix automaton is the smallest DFA that recognises all suffixes of s. It has at most 2n minus 1 states. The number of distinct substrings equals the sum over all non-root states of len[v] - len[link[v]], where len is the longest string ending at the state and link is the suffix link parent. SAM construction is O(n) with constant-alphabet assumption.

For interviews, the suffix-array-plus-LCP approach is the most commonly accepted answer. SAM is a competitive-programming flex; mention it for bonus points but be ready to defend the implementation.

Visual Dry Run / Worked Example#

Take s = "banana", length 6.

Suffixes:

0: banana
1: anana
2: nana
3: ana
4: na
5: a

Sorted lexicographically:

sa[0]=5: a
sa[1]=3: ana
sa[2]=1: anana
sa[3]=0: banana
sa[4]=4: na
sa[5]=2: nana

LCP between adjacent sorted suffixes:

lcp(a, ana) = 1     ("a")
lcp(ana, anana) = 3 ("ana")
lcp(anana, banana) = 0
lcp(banana, na) = 0
lcp(na, nana) = 2   ("na")

Total prefixes = sum of suffix lengths = 1 + 3 + 5 + 6 + 2 + 4 = 21.

Sum of LCPs = 1 + 3 + 0 + 0 + 2 = 6.

Distinct substrings = 21 - 6 = 15.

Sanity check: enumerate banana's substrings — a, b, n, an, ba, na, ana, ban, nan, anan, bana, nana, anana, banan, banana. Fifteen unique substrings. The formula matches.

Solution (Optimal)#

Python — Suffix Array via doubling + Kasai LCP#

def countDistinctSubstrings(s):
    n = len(s)
    if n == 0:
        return 0
 
    # Build suffix array via sort (O(n^2 log n) in Python; replace with doubling for production)
    sa = sorted(range(n), key=lambda i: s[i:])
 
    rank = [0] * n
    for i, suf in enumerate(sa):
        rank[suf] = i
 
    # Kasai's algorithm for LCP O(n)
    lcp = [0] * (n - 1) if n > 1 else []
    h = 0
    for i in range(n):
        if rank[i] > 0:
            j = sa[rank[i] - 1]
            while i + h < n and j + h < n and s[i + h] == s[j + h]:
                h += 1
            lcp[rank[i] - 1] = h
            if h > 0:
                h -= 1
        else:
            h = 0
 
    total_prefixes = n * (n + 1) // 2
    return total_prefixes - sum(lcp)

JavaScript — Suffix Array + Kasai LCP#

function countDistinctSubstrings(s) {
  const n = s.length;
  if (n === 0) return 0;
 
  const sa = Array.from({ length: n }, (_, i) => i);
  sa.sort((a, b) => {
    const sa1 = s.slice(a), sb1 = s.slice(b);
    return sa1 < sb1 ? -1 : sa1 > sb1 ? 1 : 0;
  });
 
  const rank = new Array(n);
  sa.forEach((suf, i) => { rank[suf] = i; });
 
  const lcp = new Array(Math.max(0, n - 1)).fill(0);
  let h = 0;
  for (let i = 0; i < n; i++) {
    if (rank[i] > 0) {
      const j = sa[rank[i] - 1];
      while (i + h < n && j + h < n && s[i + h] === s[j + h]) h++;
      lcp[rank[i] - 1] = h;
      if (h > 0) h--;
    } else {
      h = 0;
    }
  }
 
  const totalPrefixes = (n * (n + 1)) / 2;
  let lcpSum = 0;
  for (const v of lcp) lcpSum += v;
  return totalPrefixes - lcpSum;
}

Complexity assuming a true O(n log n) suffix array: O(n log n) overall. Memory O(n).

Rolling-hash alternative (Python sketch)#

def countDistinctSubstrings_hash(s):
    MOD = (1 << 61) - 1
    BASE = 131
    n = len(s)
    seen = set()
    for i in range(n):
        h = 0
        for j in range(i, n):
            h = (h * BASE + ord(s[j])) % MOD
            seen.add(h)
    return len(seen)

O(n^2) time, O(n^2) memory. Watch for hash collisions; double hashing is safer for adversarial inputs.

Common Mistakes#

• Generating all O(n^2) substrings as Python slices — works for n up to a few thousand but blows memory beyond that.
• Forgetting Kasai's invariant — the running h decreases by at most 1 per iteration, which is what gives the O(n) bound. Resetting h = 0 every iteration gives O(n^2).
• Off-by-one between sa and rank. sa[i] is the starting index of the i-th sorted suffix. rank[suf] = i is the inverse mapping.
• Using a single rolling-hash modulus on adversarial inputs. Use double hashing or a large prime modulus to dodge collisions.
• Forgetting the empty suffix. This problem usually counts non-empty substrings; the formula above already excludes the empty string.

Interview Tips#

Open with the brute force. State that there are O(n^2) substrings and that deduplicating naively is at least O(n^3) without hashing. Mention rolling hash as a O(n^2) average-time solution.

Then describe the suffix-array structure. Walk through the visual example slowly — sorted suffixes, then LCPs, then the formula. Interviewers grade for understanding why subtracting LCPs gives distinct substrings.

If pressed for sub-O(n log n), mention the suffix automaton: its size is linear in n, and the answer is the sum of len[v] - len[link[v]] across non-root states. Be ready to sketch SAM construction.

If short on time, code the rolling-hash version with double hashing. Interviewers usually accept it as long as you mention hash-collision risk and the more efficient suffix-array alternative.

Follow-up Questions#

1. Count distinct substrings of length exactly k. Sum max(0, k - lcp[i]) over consecutive sorted suffixes that have suffix length at least k.
2. Longest repeated substring. It is max(lcp) from the LCP array.
3. Number of substrings appearing at least twice. Subtract distinct from total — or compute directly from the LCP array.
4. Online distinct substring count as characters arrive. Use the suffix automaton; each character adds at most 2 new states and the running answer increments by len[last] - len[link[last]].
5. Distinct substrings of two strings combined. Build a generalised suffix array on s + '#' + t + '$', or a generalised suffix automaton.

Key Takeaways#

• Counting distinct substrings is the canonical entry point to suffix-data-structure techniques.
• The classical formula n(n+1)/2 - sum(LCP) reduces the problem to computing a suffix array plus the LCP array via Kasai.
• Suffix arrays plus LCP run in O(n log n), or O(n) with DC3 and SA-IS construction.
• Suffix automata achieve O(n) total work and the answer is the sum of len[v] - len[link[v]].
• Rolling hash is a viable O(n^2) backup; always pair it with double hashing or large-prime moduli to guard against collisions.
• Once you can count distinct substrings via a suffix array, you have the toolbox for longest repeated substring, longest common substring, and many other classic string problems.