Topics › Tries › Problems

Number of distinct substrings in a string

Medium TUF ID 1026 A2ZSDE

LeetCode ↗ Java source ↗ Edit this article ↗

Problem

Given a string s of lowercase letters, count its distinct substrings. A substring is a contiguous block s[i..j]. Two substrings are the same if they spell the same string, wherever they occur. Following the sheet’s version, the empty substring counts as one. LeetCode 1698 counts only non-empty substrings, so its answer is ours minus 1.

The sheet’s version uses short strings, so an O(n^2) solution is what is expected there. The last approach also handles lengths around 10^5.

Example 1

s = "aba"
answer = 6      // "", "a", "b", "ab", "ba", "aba"; "a" occurs twice but is counted once

Example 2

s = "aaaa"
answer = 5      // "", "a", "aa", "aaa", "aaaa"

One observation drives the two faster approaches: every substring is a prefix of some suffix. s[i..j] is the first j - i + 1 characters of the suffix that starts at i. Counting distinct substrings is therefore the same as counting the distinct prefixes of all suffixes.

Approach 1: Brute force with a hash set

Intuition. Generate every substring and let a HashSet throw away the repeats. The set’s size is the number of distinct non-empty substrings; add 1 for the empty one.

Algorithm.

For every start i and every end j > i, add s.substring(i, j) to the set.
Return set.size() + 1.

static long bruteForce(String s) {
    Set<String> seen = new HashSet<>();
    for (int i = 0; i < s.length(); i++) {
        for (int j = i + 1; j <= s.length(); j++) {
            seen.add(s.substring(i, j));               // copying s[i..j-1] costs O(j - i)
        }
    }
    return seen.size() + 1L;                           // + 1 for the empty substring
}

Complexity. Time O(n^3): there are n(n + 1) / 2 substrings and each one is copied and hashed in time proportional to its length. Space O(n^3) characters in the worst case, because the set keeps a full copy of every distinct substring. For n = 1000 that can approach 1.7 × 10^8 characters (about n^3 / 6), which is too much memory even if the time passes.

Approach 2: Better, a trie of all suffixes

Intuition. Insert every suffix of s into a trie. Each node below the root spells a string that is a prefix of some suffix, which makes it a substring. Each distinct substring has exactly one node, because a string determines its path from the root. So the number of distinct non-empty substrings equals the number of nodes in the trie, not counting the root.

We do not even need to count afterwards. While inserting the suffix that starts at i, the step for character j either follows an existing edge, meaning s[i..j] was already seen, or creates a node, meaning s[i..j] is new. Counting the nodes as they are created gives the answer, and no substring is ever copied.

Algorithm.

Create an empty root. Set created = 0.
For each start i: walk from the root over s[i], s[i+1], ...; whenever a child is missing, create it and increment created.
Return created + 1. The root stands for the empty substring.

static class TrieNode {
    final TrieNode[] child = new TrieNode[26];
}

static long better(String s) {
    TrieNode root = new TrieNode();
    long created = 0;
    for (int i = 0; i < s.length(); i++) {             // suffix starting at i
        TrieNode cur = root;
        for (int j = i; j < s.length(); j++) {         // its prefixes are the substrings s[i..j]
            int c = s.charAt(j) - 'a';
            if (cur.child[c] == null) {
                cur.child[c] = new TrieNode();
                created++;                             // s[i..j] has not appeared before
            }
            cur = cur.child[c];
        }
    }
    return created + 1;                                // the root stands for the empty substring
}

Dry run on "aba":

Suffix	Path walked	New nodes	`created`
`aba` (i = 0)	a, ab, aba	3	3
`ba` (i = 1)	b, ba	2	5
`a` (i = 2)	a, already there	0	5

Answer 5 + 1 = 6.

Complexity. Time O(n^2): the inner loop runs n(n + 1) / 2 times and does constant work each time. Space O(n^2) nodes in the worst case, one per distinct substring, each holding 26 references. That memory bill is the trie’s weakness. A string of length 10^5 with mostly distinct substrings would need billions of nodes.

This is the solution the sheet expects in the trie section. The next approach is for when n is too large for n^2.

Approach 3: Optimal, suffix array and LCP

Intuition. The trie stores every prefix of every suffix explicitly. We can get the same count from much less information. Sort all suffixes lexicographically. Suffix sa[i] (the i-th smallest) has n - sa[i] non-empty prefixes. Some of them were already counted for earlier suffixes, and in sorted order the earlier suffix sharing the most with it is its immediate predecessor sa[i - 1]. Any earlier suffix shares at most as much, because suffixes sharing a longer start would sort between them. So exactly lcp[i] of its prefixes are old, where lcp[i] is the length of the longest common prefix of sa[i - 1] and sa[i], and the rest are new:

answer = 1 + Σ over i of ( (n - sa[i]) - lcp[i] )        with lcp[0] = 0

Two standard pieces build the inputs.

Suffix array by prefix doubling. Rank the suffixes by their first character. If every suffix has a rank for its first k characters, then the pair (rank[i], rank[i + k]) ranks its first 2k characters, because those 2k characters are the first k of suffix i followed by the first k of suffix i + k. A suffix with fewer than k characters left gets -1 as its second component, so it sorts before anything it is a prefix of. Sort by the pairs, renumber, and double k. After at most log n rounds all ranks differ and the order is final.

static int[] suffixArray(String s) {
    int n = s.length();
    Integer[] order = new Integer[n];
    int[] rank = new int[n], next = new int[n];
    for (int i = 0; i < n; i++) {
        order[i] = i;
        rank[i] = s.charAt(i);
    }
    for (int k = 1; n > 1; k <<= 1) {
        final int step = k;
        Comparator<Integer> byPair = (a, b) -> {       // compare (rank of first k chars, rank of next k chars)
            if (rank[a] != rank[b]) return Integer.compare(rank[a], rank[b]);
            int ra = a + step < n ? rank[a + step] : -1;   // a suffix that runs out sorts first
            int rb = b + step < n ? rank[b + step] : -1;
            return Integer.compare(ra, rb);
        };
        Arrays.sort(order, byPair);
        next[order[0]] = 0;
        for (int i = 1; i < n; i++) {
            next[order[i]] = next[order[i - 1]] + (byPair.compare(order[i - 1], order[i]) < 0 ? 1 : 0);
        }
        System.arraycopy(next, 0, rank, 0, n);
        if (rank[order[n - 1]] == n - 1) break;        // all ranks distinct: fully sorted
    }
    int[] sa = new int[n];
    for (int i = 0; i < n; i++) sa[i] = order[i];
    return sa;
}

LCP by Kasai’s algorithm. Process suffixes in text order i = 0, 1, 2, ... and compare each with its predecessor in sorted order. If suffix i shares h ≥ 1 characters with its predecessor j, drop the first character from both: suffix j + 1 is still smaller than suffix i + 1 and shares h - 1 characters with it. Whatever sits directly before i + 1 in sorted order lies between them, so it shares at least h - 1 characters too. So the match length h falls by at most 1 per step and never restarts from zero. It increases at most 2n times overall, which makes the whole pass O(n).

static int[] lcpArray(String s, int[] sa) {
    int n = s.length();
    int[] pos = new int[n], lcp = new int[n];
    for (int i = 0; i < n; i++) pos[sa[i]] = i;
    int h = 0;
    for (int i = 0; i < n; i++) {                      // suffixes in text order: h drops by at most 1 each step
        if (pos[i] == 0) {
            h = 0;
            continue;
        }
        int j = sa[pos[i] - 1];                        // the suffix just before suffix i in sorted order
        while (i + h < n && j + h < n && s.charAt(i + h) == s.charAt(j + h)) h++;
        lcp[pos[i]] = h;
        if (h > 0) h--;
    }
    return lcp;
}

static long optimal(String s) {
    int n = s.length();
    int[] sa = suffixArray(s);
    int[] lcp = lcpArray(s, sa);
    long total = 1;                                    // the empty substring
    for (int i = 0; i < n; i++) {
        total += (n - sa[i]) - lcp[i];                 // prefixes of suffix sa[i] not already counted
    }
    return total;
}

Dry run on "banana" (n = 6):

i	sa[i]	Suffix	lcp[i]	New substrings
0	5	a	0	1
1	3	ana	1	2
2	1	anana	3	2
3	0	banana	0	6
4	4	na	0	2
5	2	nana	2	2

The new counts add up to 15. Adding the empty substring gives 16. For example, "ana" contributes only "an" and "ana", because "a" came from the suffix before it.

Complexity. Time O(n log^2 n): up to log n rounds, each an O(n log n) sort, plus O(n) for Kasai and the final sum. Space O(n). Linear-time constructions exist (SA-IS, or a suffix automaton that counts distinct substrings directly), but they are well beyond interview scope.

Edge cases and pitfalls

Empty substring convention. Decide whether "" counts. The sheet counts it, LeetCode 1698 does not. The difference is exactly 1.
Empty input. s = "" has only the empty substring, so the answer is 1. All three methods return 1.
Overflow. A string of length 10^5 can have about 5 × 10^9 distinct substrings, more than an int holds. The methods return long.
Repeated characters. "aaaa" turns the trie into a single chain of n nodes, so the answer is n + 1. This is the cheap case for the trie and the case that needs the most doubling rounds for the suffix array.
Alphabet. The trie indexes c - 'a' and so assumes lowercase letters. The hash set and the suffix array work for any characters.
Prefix doubling sentinel. Use a rank below every real rank, here -1, for “no second half”. Otherwise a suffix and a longer suffix that starts with it can tie.

Trie Implementation and Operations is the trie used in Approach 2.
Longest Word with All Prefixes also reads its answer off the shape of a trie.
Longest common substring is another substring question, solved with DP.
Longest happy prefix compares prefixes with suffixes of the same string.