Loading…

mediumStringsSometimes asked

Count Distinct Substrings

Q: How do you solve Count Distinct Substrings using the Brute Force — Hash Every Substring approach?

When to use it: State it first; it defines correctness and motivates why we need a structure that avoids enumerating all n² substrings. The definition-driven solution: produce every substring and let a set deduplicate. **The literal method.** Loop `i` over start indices and `j` over end indices, and add `s[i..j]` to a set. After the loops, the set's cardinality is the count of distinct substrings. **Making it O(n²) instead of O(n³).** Inserting the substring *string* costs O(length) for hashing and comparison, so the literal version is O(n³). Precompute prefix hashes so any substring's polynomial hash is O(1); store hashes in the set. That removes the per-substring length factor and gives O(n²) time — but introduces collision risk, so a fully correct version would verify or use double hashing. **Why it doesn't scale.** Both time and memory are Θ(n²). At n = 10⁵ that's 10¹⁰ entries — neither the clock nor the heap survives. The approach is correct and is a fine sanity check for small n, but it enumerates exactly the thing we want to avoid enumerating. Time complexity: O(n²) average (hashing), O(n³) if comparing strings. Space complexity: O(n²).

Arrays & Hashing · 36 of 83 · 13 min

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

A substring is a contiguous slice s[i..j]. Two substrings are the same if they are equal as strings, regardless of where they occur. Count each distinct value once.

In plain English

You're counting the size of the set of all contiguous slices. The duplicates are the difficulty: the naive count n(n+1)/2 over-counts repeated slices. The optimal solution recognizes that every substring is the prefix of exactly one suffix, sorts the suffixes so equal prefixes cluster, and subtracts the shared-prefix lengths (the LCP array) from the gross count.

Examples

Example 1

Input: s = "aaa"
Output: 3
Note: Substrings: "a", "aa", "aaa" — only 3 distinct even though there are 6 total slices.

Example 2

Input: s = "abc"
Output: 6
Note: All 6 slices are distinct: a, b, c, ab, bc, abc. No duplicates to subtract.

Example 3

Input: s = "abab"
Output: 7
Note: Distinct: a, b, ab, ba, aba, bab, abab. Gross 4·5/2 = 10; ΣLCP = 3, so 10 − 3 = 7.

Constraints

1 ≤ n ≤ 10⁵ (the optimal); the hashing baseline only survives n ≤ ~3000
Lowercase/printable ASCII
Answer can be up to n(n+1)/2 ≈ 5×10⁹ for n = 10⁵ — use 64-bit
Substrings are contiguous; subsequences are a different problem

Clarifying questions4First question: Substrings or subsequences?Explore questions

Q1.Substrings or subsequences?
Substrings — contiguous. Subsequences are a separate, harder counting problem.
Q2.Empty substring counted?
No, count non-empty substrings only; that's why the gross total is n(n+1)/2.
Q3.How large is n?
Decides the approach. Up to a few thousand, hashing every substring is fine. For 10⁵, you need suffix array + LCP.
Q4.Could the answer overflow 32-bit?
Yes — for n = 10⁵ it reaches ~5×10⁹. Use a 64-bit accumulator.

Quick interview revision

Understand

30-second explanation

Build the interview-ready mental model before comparing implementations.

Count how many distinct (unique) non-empty substrings a string has. There are n(n+1)/2 substrings counting duplicates; the answer subtracts the repeats. The clean optimal: build the suffix array, then the LCP array (Kasai), and compute n(n+1)/2 − Σ LCP[i]. Each suffix contributes (its length) new substrings minus the prefix it shares with the previous suffix in sorted order. That's O(n log n) for the suffix array plus O(n) for LCP.

Interview contextWhat is testedWhere candidates slipHow to stand outExplore interview context

What's being tested

Whether you can move past the brute-force hash set to the suffix-array + LCP formula, and whether you can explain why adjacent sorted suffixes capture all duplicate substrings.

Where candidates slip

Stopping at O(n²) hashing (and forgetting it's also O(n²) memory / collision-prone), or miscounting by forgetting that LCP is taken between adjacent suffixes in sorted order only.

How to stand out

Derive distinct = n(n+1)/2 − ΣLCP from first principles, mention the suffix automaton as the O(n) alternative, and note the same machinery solves longest-repeated-substring.

Choose

Compare the available approaches

Use constraints and trade-offs to select the route you can defend in an interview.

Approaches at a glanceCompare before you dive in

#	Approach	Time	Space	When to mention	Jump
1	Brute Force — Hash Every Substring	`O(n²) average (hashing), O(n³) if comparing strings`	`O(n²)`	State it first; it defines correctness and motivates why we need a structure that avoids enumerating all n² substrings.	Read
2	Suffix Array + LCP (Optimal)Optimal	`O(n log n)`	`O(n)`	The intended answer. Build to the formula distinct = n(n+1)/2 − ΣLCP and explain each piece.	Read

Interactive decision treeInteractiveChoose the right approachFollow the branches and learn why each constraint changes the solution.Explore the full tree

From substrings to a subtraction

How to read it:Substrings are prefixes of suffixes; sorting suffixes makes duplicate prefixes adjacent so LCP counts the repeats.

Rendering diagram…

Learn & trace

Build each solution step by step

Move from the core idea to a visual trace, implementation, proof, and edge cases.

03.1

Approach 1 of 2

Brute Force — Hash Every Substring

TimeO(n²) average (hashing), O(n³) if comparing stringsSpaceO(n²)

State it first; it defines correctness and motivates why we need a structure that avoids enumerating all n² substrings.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

Enumerate every substring s[i..j] and insert it into a hash set; the set's size is the answer.

2Hint 2Explore hint

There are about n²/2 substrings. Inserting each O(1)-ish with a precomputed rolling hash gives O(n²); inserting raw strings costs an extra O(n) each.

3Hint 3Explore hint

Both the time and the memory grow as n² — that's the ceiling that suffix structures break.

A · Core idea

The definition-driven solution: produce every substring and let a set deduplicate.

The literal method. Loop i over start indices and j over end indices, and add s[i..j] to a set. After the loops, the set's cardinality is the count of distinct substrings.

Making it O(n²) instead of O(n³). Inserting the substring string costs O(length) for hashing and comparison, so the literal version is O(n³). Precompute prefix hashes so any substring's polynomial hash is O(1); store hashes in the set. That removes the per-substring length factor and gives O(n²) time — but introduces collision risk, so a fully correct version would verify or use double hashing.

Why it doesn't scale. Both time and memory are Θ(n²). At n = 10⁵ that's 10¹⁰ entries — neither the clock nor the heap survives. The approach is correct and is a fine sanity check for small n, but it enumerates exactly the thing we want to avoid enumerating.

B · Visual dry run

Interactive dry run

Select a frame to connect the decision with its visual state.

s = "abab"

Hash-map state

after len 1

ValueIndex / state

a→ ✓

b→ ✓

Continue scanning

a and b inserted, duplicates ignored

Final result7

C · Code with teaching comments

Reference implementation previewimport java.util.HashSet; import java.util.Set; public class BruteForceDistinct { public long countDistinct(String s) {Explore the full code

solution.javaJava

Brute Force — Hash Every Substring — reference

2 teaching notes

1
import java.util.HashSet;
2
import java.util.Set;
3
 
4
public class BruteForceDistinct {
5
    public long countDistinct(String s) {
6
        int n = s.length();
7
        Set<String> seen = new HashSet<>();
8
        for (int i = 0; i < n; i++) {
9
            // j is exclusive end; this nested loop generates all n(n+1)/2 substrings.
10
            for (int j = i + 1; j <= n; j++) {
11
                // The set deduplicates; substring() itself is O(length), pushing this
12
                // toward O(n³).
13
                seen.add(s.substring(i, j));
14
            }
15
        }
16
        return seen.size();
17
    }
18
 
19
    public static void main(String[] args) {
20
        System.out.println(new BruteForceDistinct().countDistinct("abab"));
21
    }
22
}

Yellow row = the algorithm's core logic. Amber `//` lines above it = what you'd say out loud.22 lines

D · Why it works and complexityO(n²) average (hashing), O(n³) if comparing strings timeO(n²) spaceOpen the invariant and proofExplore the proof

Hashing every substring treats each substring as independent, ignoring that substrings overlap massively. The suffix-array view exploits that overlap: equal substrings become equal prefixes of suffixes, which cluster when sorted.

ComplexityO(n²) average (hashing), O(n³) if comparing strings time, O(n²) space — n(n+1)/2 substrings. With a rolling/prefix hash, each substring's hash is O(1) to derive and O(1) to insert → O(n²) time. Storing them is O(n²) space. Comparing actual strings instead of hashes would add an O(n) factor (O(n³)).

E · Edge cases and pitfalls3Returning an int — the count overflows 32-bit for large n.Explore edge cases

Pitfalls

Returning an int — the count overflows 32-bit for large n.
Believing the hash-set version is O(n) memory — it's O(n²).
Using raw string hashing without verification and assuming zero collisions.

03.2

Approach 2 of 2 · Optimal

Suffix Array + LCP (Optimal)

TimeO(n log n)SpaceO(n)

The intended answer. Build to the formula distinct = n(n+1)/2 − ΣLCP and explain each piece.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

Reframe: every substring is a prefix of some suffix of s. So counting distinct substrings = counting distinct prefixes across all suffixes.

2Hint 2Explore hint

If you sort the suffixes, two suffixes that share a long prefix sit next to each other. The shared prefix is exactly the duplicated substrings between them.

3Hint 3Explore hint

Suffix i alone contributes (n − SA[i]) prefixes; subtract LCP[i], the prefix it shares with the previous sorted suffix, to avoid double counting. Summing gives n(n+1)/2 − ΣLCP.

A · Core idea

The optimal solution rests on two reframings and one formula.

Reframing 1 — substrings are prefixes of suffixes. Any substring s[i..j] is the prefix of length j−i+1 of the suffix that starts at i. So the set of all substrings equals the set of all prefixes of all suffixes. Counting distinct substrings becomes counting distinct prefixes over every suffix.

Reframing 2 — sort the suffixes. Build the suffix array SA: the indices of all n suffixes sorted lexicographically. Why sort? Because two suffixes that begin with the same characters end up adjacent, so any prefix shared by two different suffixes is shared by adjacent sorted suffixes. That localizes all duplication to neighboring pairs.

The LCP array does the counting. LCP[i] is the length of the longest common prefix of SA[i] and SA[i−1] (consecutive sorted suffixes). Consider the suffixes in sorted order. The suffix at SA[i] has length n − SA[i], contributing that many prefixes. But the first LCP[i] of those prefixes already appeared as prefixes of the previous suffix SA[i−1] — they're duplicates. So this suffix contributes (n − SA[i]) − LCP[i] new distinct substrings.

The formula. Summing the new contributions over all suffixes, the lengths sum to n(n+1)/2 (each suffix's full length, which is just the gross count of all substrings) and the LCPs sum to the total duplication: distinct = n(n+1)/2 − Σ LCP[i]. The first suffix has no predecessor, so its LCP is 0 and it contributes its full length.

Building the pieces efficiently. The suffix array uses prefix doubling: rank suffixes by their first character, then repeatedly double the compared length using previous ranks, re-sorting by (rank[i], rank[i+k]) pairs. That's O(n log n) ranks with O(log n) rounds. Kasai's algorithm computes LCP in O(n) by processing suffixes in original-string order and reusing the fact that the LCP can shrink by at most one when you move from suffix i to suffix i+1.

An aside on the O(n) variant. A suffix automaton counts distinct substrings in true O(n) by summing len(state) − len(link(state)) over states. Mention it as the asymptotically tighter option; the suffix-array route is the more commonly expected derivation in interviews.

B · Visual dry run

Interactive dry run

Select a frame to connect the decision with its visual state.

s = "abab"

Array state

SA order

"ab", "abab", "b", "bab"

SA0 ↓

[0]

abab

[1]

[2]

bab

[3]

Current pointerResolved stateNot processed

Final result7

C · Code with teaching comments

solution.javaJava

Suffix Array + LCP (Optimal) — optimal

5 teaching notes

1
import java.util.Arrays;
2
 
3
public class DistinctSubstrings {
4
    public int[] suffixArray(String s) {
5
        int n = s.length();
6
        Integer[] sa = new Integer[n];
7
        int[] rank = new int[n];
8
        int[] tmp = new int[n];
9
        for (int i = 0; i < n; i++) { sa[i] = i; rank[i] = s.charAt(i); }
10
        for (int k = 1; ; k <<= 1) {
11
            final int kk = k;
12
            final int[] r = rank;
13
            // Prefix-doubling: sort suffixes by their (rank, next-rank) pair, doubling
14
            // the compared length each round.
15
            Arrays.sort(sa, (a, b) -> {
16
                if (r[a] != r[b]) return Integer.compare(r[a], r[b]);
17
                int ra = a + kk < n ? r[a + kk] : -1;
18
                int rb = b + kk < n ? r[b + kk] : -1;
19
                return Integer.compare(ra, rb);
20
            });
21
            tmp[sa[0]] = 0;
22
            for (int i = 1; i < n; i++) {
23
                int prev = sa[i - 1], cur = sa[i];
24
                int pra = prev + kk < n ? r[prev + kk] : -1;
25
                int cra = cur + kk < n ? r[cur + kk] : -1;
26
                boolean same = r[prev] == r[cur] && pra == cra;
27
                tmp[cur] = tmp[prev] + (same ? 0 : 1);
28
            }
29
            System.arraycopy(tmp, 0, rank, 0, n);
30
            // All ranks distinct → suffixes are fully ordered, stop doubling.
31
            if (rank[sa[n - 1]] == n - 1) break;
32
        }
33
        int[] out = new int[n];
34
        for (int i = 0; i < n; i++) out[i] = sa[i];
35
        return out;
36
    }
37
 
38
    public int[] kasaiLcp(String s, int[] sa) {
39
        int n = s.length();
40
        int[] rank = new int[n];
41
        for (int i = 0; i < n; i++) rank[sa[i]] = i;
42
        int[] lcp = new int[n];
43
        int h = 0;
44
        for (int i = 0; i < n; i++) {
45
            if (rank[i] > 0) {
46
                int j = sa[rank[i] - 1];
47
                // Kasai extends the LCP; h carries over and drops by at most 1, giving
48
                // amortized O(n).
49
                while (i + h < n && j + h < n && s.charAt(i + h) == s.charAt(j + h)) h++;
50
                lcp[rank[i]] = h;
51
                if (h > 0) h--;
52
            } else {
53
                h = 0;
54
            }
55
        }
56
        return lcp;
57
    }
58
 
59
    public long countDistinct(String s) {
60
        int n = s.length();
61
        if (n == 0) return 0;
62
        int[] sa = suffixArray(s);
63
        int[] lcp = kasaiLcp(s, sa);
64
        // Gross substring count; long avoids overflow at ~5×10⁹.
65
        long total = (long) n * (n + 1) / 2;
66
        // Subtract every shared-prefix length — the formula distinct = n(n+1)/2 − ΣLCP.
67
        for (int v : lcp) total -= v;
68
        return total;
69
    }
70
 
71
    public static void main(String[] args) {
72
        System.out.println(new DistinctSubstrings().countDistinct("abab"));
73
    }
74
}

Yellow row = the algorithm's core logic. Amber `//` lines above it = what you'd say out loud.74 lines

D · Why it works and complexityO(n log n) timeO(n) spaceOpen the invariant and proofExplore the proof

The leap is seeing that 'distinct substrings' equals 'distinct prefixes of suffixes', because then sorting makes all duplicate prefixes adjacent and the LCP array measures exactly the over-count. The whole problem collapses to one subtraction: gross count minus shared prefixes.

ComplexityO(n log n) time, O(n) space — Suffix array by prefix-doubling is O(n log n) (O(n log² n) with comparison sort, O(n log n) with radix). Kasai's LCP is O(n) amortized — the helper length h drops by at most 1 between steps. The final sum is O(n). Overall O(n log n) time, O(n) space.

E · Edge cases and pitfalls7s = "aaa" — SA = [2,1,0]; LCP = [0,1,2]; 6 − 3 = 3 distinct.Explore edge cases

Edge cases handled

s = "aaa"SA = [2,1,0]; LCP = [0,1,2]; 6 − 3 = 3 distinct.
s = "a"n=1, gross = 1, ΣLCP = 0 → 1.
all distinct chars "abc"ΣLCP = 0 → n(n+1)/2 = 6, every substring unique.

Pitfalls

Taking LCP between non-adjacent suffixes — only adjacent sorted pairs are correct.
Using a 32-bit accumulator for n(n+1)/2 — overflows for large n.
Computing rank from SA incorrectly in Kasai — rank[sa[i]] = i, not the reverse.
Forgetting that the first sorted suffix contributes its full length (LCP[0] = 0).

Practice

Try the solution yourself

Edit the optimal implementation, test another input, and observe the result.

Editable code previewimport java.util.Arrays; public class DistinctSubstrings { public int[] suffixArray(String s) { int n = s.length();Explore the playground

Try it — Java· run a complete program; method snippets need a driver

import java.util.Arrays;

public class DistinctSubstrings {
    public int[] suffixArray(String s) {
        int n = s.length();
        Integer[] sa = new Integer[n];
        int[] rank = new int[n];
        int[] tmp = new int[n];
        for (int i = 0; i < n; i++) { sa[i] = i; rank[i] = s.charAt(i); }
        for (int k = 1; ; k <<= 1) {
            final int kk = k;
            final int[] r = rank;
            Arrays.sort(sa, (a, b) -> {
                if (r[a] != r[b]) return Integer.compare(r[a], r[b]);
                int ra = a + kk < n ? r[a + kk] : -1;
                int rb = b + kk < n ? r[b + kk] : -1;
                return Integer.compare(ra, rb);
            });
            tmp[sa[0]] = 0;
            for (int i = 1; i < n; i++) {
                int prev = sa[i - 1], cur = sa[i];
                int pra = prev + kk < n ? r[prev + kk] : -1;
                int cra = cur + kk < n ? r[cur + kk] : -1;
                boolean same = r[prev] == r[cur] && pra == cra;
                tmp[cur] = tmp[prev] + (same ? 0 : 1);
            }
            System.arraycopy(tmp, 0, rank, 0, n);
            if (rank[sa[n - 1]] == n - 1) break;
        }
        int[] out = new int[n];
        for (int i = 0; i < n; i++) out[i] = sa[i];
        return out;
    }

public int[] kasaiLcp(String s, int[] sa) {
        int n = s.length();
        int[] rank = new int[n];
        for (int i = 0; i < n; i++) rank[sa[i]] = i;
        int[] lcp = new int[n];
        int h = 0;
        for (int i = 0; i < n; i++) {
            if (rank[i] > 0) {
                int j = sa[rank[i] - 1];
                while (i + h < n && j + h < n && s.charAt(i + h) == s.charAt(j + h)) h++;
                lcp[rank[i]] = h;
                if (h > 0) h--;
            } else {
                h = 0;
            }
        }
        return lcp;
    }

public long countDistinct(String s) {
        int n = s.length();
        if (n == 0) return 0;
        int[] sa = suffixArray(s);
        int[] lcp = kasaiLcp(s, sa);
        long total = (long) n * (n + 1) / 2;
        for (int v : lcp) total -= v;
        return total;
    }

public static void main(String[] args) {
        System.out.println(new DistinctSubstrings().countDistinct("abab"));
    }
}

Avoid mistakes

Recognize the interview traps

Understand why common attempts fail before reviewing the corrected implementation.

Stopping at the hash-set baseline

It enumerates all n²/2 substrings in both time and memory. For n = 10⁵ that is 10¹⁰ entries — it will not finish or fit. The interviewer expects the suffix-array reduction.

Explore the code comparison

Don't write this

seen = {s[i:j] for i in range(n) for j in range(i + 1, n + 1)}
return len(seen)   # O(n^2) time AND memory

Write this instead

sa = suffix_array(s)
lcp = kasai_lcp(s, sa)
return n * (n + 1) // 2 - sum(lcp)

Wrong rank inversion in Kasai

Kasai needs rank[i] = position of suffix i in SA. Writing sa[rank[i]] or inverting the assignment gives garbage LCPs.

Explore the code comparison

Don't write this

for (int i = 0; i < n; i++) rank[i] = sa[i]; // WRONG direction

Write this instead

for (int i = 0; i < n; i++) rank[sa[i]] = i; // rank is the inverse of SA

32-bit overflow on the gross count

n(n+1)/2 reaches ~5×10⁹ at n = 10⁵, past the 32-bit limit, so the subtraction underflows into a wrong (often negative) answer.

Explore the code comparison

Don't write this

int total = n * (n + 1) / 2; // overflows

Write this instead

long total = (long) n * (n + 1) / 2;

Revise

Carry the pattern into the interview

Quick interview revision

Pattern to remember

Suffix array + LCP: total substrings minus shared prefixes

Code pattern to memorize

distinct = n*(n+1)/2 - sum(LCP[i] for i in 1..n-1)
  where SA = sorted suffixes, LCP[i] = longest common prefix of SA[i] and SA[i-1]

Rules to remember

1Every substring is a prefix of some suffix — that reframing is the whole reason suffixes show up.
2Sort the suffixes; adjacent sorted suffixes share the most prefix, so LCP[i] counts exactly the duplicate substrings to subtract.
3Total substrings with duplicates is n(n+1)/2; distinct = that minus Σ LCP.
4The O(n²) hashing baseline stores every substring's hash in a set — correct, but O(n²) time and space, and risks collisions without verification.
5Use a separator-free input here; suffix arrays don't need one, unlike the Z/KMP concatenation trick.

Use this pattern when

Counting unique substrings, or unique substrings of a given length
Any problem reducible to 'distinct prefixes of suffixes'
Longest repeated substring, longest common substring of two strings
When you already need a suffix array/automaton for other queries

Choose another pattern when

n is tiny (≤ a few thousand) and you just need a quick answer → the hashing set is simpler to write
You need online/streaming updates → suffix automaton incremental construction
Only counting occurrences of one fixed pattern → KMP/Z, not a full suffix structure
Memory is extremely tight → suffix array uses O(n) ints; a hash set of substrings is far worse

Interview takeaway

Two reframings carry the whole problem: substrings are prefixes of suffixes, and sorting suffixes makes duplicate prefixes adjacent. The LCP array then turns 'count distinct' into one subtraction.

Continue

Transfer the pattern to another problem

Use a direct variation or pattern sibling to prove the idea is reusable.

Transferable patternSuffix Array + LCP. Recognise it for any 'distinct / repeated / common substring' question: the SA clusters equal prefixes and the LCP array measures their overlap, turning enumeration into arithmetic.

Practice queueDirect variations and pattern siblings

Direct follow-ups

Longest Repeated Substring
Coming soon
The maximum value in the LCP array is the length of the longest substring that appears at least twice.
Longest Common Substring of Two Strings
Coming soon
Concatenate with a separator, build SA+LCP, take the max LCP between suffixes originating from different strings.
Count Distinct Substrings of Each Length
Coming soon
Use the LCP array bucketed by length, or a suffix automaton's per-state contributions.
Distinct Substrings via Suffix Automaton (O(n))
Coming soon
Sum len(state) − len(link(state)) over all states for a true linear-time count.

←

Strong Password

Continue · Next problem

Lexicographic Rank of a String

mediumStringsSometimes asked

Count Distinct Substrings

Arrays & Hashing · 36 of 83 · 13 min

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

A substring is a contiguous slice s[i..j]. Two substrings are the same if they are equal as strings, regardless of where they occur. Count each distinct value once.

In plain English

Examples

Example 1

Input: s = "aaa"
Output: 3
Note: Substrings: "a", "aa", "aaa" — only 3 distinct even though there are 6 total slices.

Example 2

Input: s = "abc"
Output: 6
Note: All 6 slices are distinct: a, b, c, ab, bc, abc. No duplicates to subtract.

Example 3

Input: s = "abab"
Output: 7
Note: Distinct: a, b, ab, ba, aba, bab, abab. Gross 4·5/2 = 10; ΣLCP = 3, so 10 − 3 = 7.

Constraints

1 ≤ n ≤ 10⁵ (the optimal); the hashing baseline only survives n ≤ ~3000
Lowercase/printable ASCII
Answer can be up to n(n+1)/2 ≈ 5×10⁹ for n = 10⁵ — use 64-bit
Substrings are contiguous; subsequences are a different problem

Clarifying questions4First question: Substrings or subsequences?Explore questions

Q1.Substrings or subsequences?
Substrings — contiguous. Subsequences are a separate, harder counting problem.
Q2.Empty substring counted?
No, count non-empty substrings only; that's why the gross total is n(n+1)/2.
Q3.How large is n?
Decides the approach. Up to a few thousand, hashing every substring is fine. For 10⁵, you need suffix array + LCP.
Q4.Could the answer overflow 32-bit?
Yes — for n = 10⁵ it reaches ~5×10⁹. Use a 64-bit accumulator.

Quick interview revision

Understand

30-second explanation

Build the interview-ready mental model before comparing implementations.

Interview contextWhat is testedWhere candidates slipHow to stand outExplore interview context

What's being tested

Whether you can move past the brute-force hash set to the suffix-array + LCP formula, and whether you can explain why adjacent sorted suffixes capture all duplicate substrings.

Where candidates slip

Stopping at O(n²) hashing (and forgetting it's also O(n²) memory / collision-prone), or miscounting by forgetting that LCP is taken between adjacent suffixes in sorted order only.

How to stand out

Derive distinct = n(n+1)/2 − ΣLCP from first principles, mention the suffix automaton as the O(n) alternative, and note the same machinery solves longest-repeated-substring.

Choose

Compare the available approaches

Use constraints and trade-offs to select the route you can defend in an interview.

Approaches at a glanceCompare before you dive in

#	Approach	Time	Space	When to mention	Jump
1	Brute Force — Hash Every Substring	`O(n²) average (hashing), O(n³) if comparing strings`	`O(n²)`	State it first; it defines correctness and motivates why we need a structure that avoids enumerating all n² substrings.	Read
2	Suffix Array + LCP (Optimal)Optimal	`O(n log n)`	`O(n)`	The intended answer. Build to the formula distinct = n(n+1)/2 − ΣLCP and explain each piece.	Read

Interactive decision treeInteractiveChoose the right approachFollow the branches and learn why each constraint changes the solution.Explore the full tree

From substrings to a subtraction

How to read it:Substrings are prefixes of suffixes; sorting suffixes makes duplicate prefixes adjacent so LCP counts the repeats.

Rendering diagram…

Learn & trace

Build each solution step by step

Move from the core idea to a visual trace, implementation, proof, and edge cases.

03.1

Approach 1 of 2

Brute Force — Hash Every Substring

TimeO(n²) average (hashing), O(n³) if comparing stringsSpaceO(n²)

State it first; it defines correctness and motivates why we need a structure that avoids enumerating all n² substrings.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

Enumerate every substring s[i..j] and insert it into a hash set; the set's size is the answer.

2Hint 2Explore hint

There are about n²/2 substrings. Inserting each O(1)-ish with a precomputed rolling hash gives O(n²); inserting raw strings costs an extra O(n) each.

3Hint 3Explore hint

Both the time and the memory grow as n² — that's the ceiling that suffix structures break.

A · Core idea

The definition-driven solution: produce every substring and let a set deduplicate.

The literal method. Loop i over start indices and j over end indices, and add s[i..j] to a set. After the loops, the set's cardinality is the count of distinct substrings.

B · Visual dry run

Interactive dry run

Select a frame to connect the decision with its visual state.

s = "abab"

Hash-map state

after len 1

ValueIndex / state

a→ ✓

b→ ✓

Continue scanning

a and b inserted, duplicates ignored

Final result7

C · Code with teaching comments

Reference implementation previewimport java.util.HashSet; import java.util.Set; public class BruteForceDistinct { public long countDistinct(String s) {Explore the full code

solution.javaJava

Brute Force — Hash Every Substring — reference

2 teaching notes

1
import java.util.HashSet;
2
import java.util.Set;
3
 
4
public class BruteForceDistinct {
5
    public long countDistinct(String s) {
6
        int n = s.length();
7
        Set<String> seen = new HashSet<>();
8
        for (int i = 0; i < n; i++) {
9
            // j is exclusive end; this nested loop generates all n(n+1)/2 substrings.
10
            for (int j = i + 1; j <= n; j++) {
11
                // The set deduplicates; substring() itself is O(length), pushing this
12
                // toward O(n³).
13
                seen.add(s.substring(i, j));
14
            }
15
        }
16
        return seen.size();
17
    }
18
 
19
    public static void main(String[] args) {
20
        System.out.println(new BruteForceDistinct().countDistinct("abab"));
21
    }
22
}

Yellow row = the algorithm's core logic. Amber `//` lines above it = what you'd say out loud.22 lines

D · Why it works and complexityO(n²) average (hashing), O(n³) if comparing strings timeO(n²) spaceOpen the invariant and proofExplore the proof

E · Edge cases and pitfalls3Returning an int — the count overflows 32-bit for large n.Explore edge cases

Pitfalls

Returning an int — the count overflows 32-bit for large n.
Believing the hash-set version is O(n) memory — it's O(n²).
Using raw string hashing without verification and assuming zero collisions.

03.2

Approach 2 of 2 · Optimal

Suffix Array + LCP (Optimal)

TimeO(n log n)SpaceO(n)

The intended answer. Build to the formula distinct = n(n+1)/2 − ΣLCP and explain each piece.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

Reframe: every substring is a prefix of some suffix of s. So counting distinct substrings = counting distinct prefixes across all suffixes.

2Hint 2Explore hint

If you sort the suffixes, two suffixes that share a long prefix sit next to each other. The shared prefix is exactly the duplicated substrings between them.

3Hint 3Explore hint

Suffix i alone contributes (n − SA[i]) prefixes; subtract LCP[i], the prefix it shares with the previous sorted suffix, to avoid double counting. Summing gives n(n+1)/2 − ΣLCP.

A · Core idea

The optimal solution rests on two reframings and one formula.

B · Visual dry run

Interactive dry run

Select a frame to connect the decision with its visual state.

s = "abab"

Array state

SA order

"ab", "abab", "b", "bab"

SA0 ↓

[0]

abab

[1]

[2]

bab

[3]

Current pointerResolved stateNot processed

Final result7

C · Code with teaching comments

solution.javaJava

Suffix Array + LCP (Optimal) — optimal

5 teaching notes

1
import java.util.Arrays;
2
 
3
public class DistinctSubstrings {
4
    public int[] suffixArray(String s) {
5
        int n = s.length();
6
        Integer[] sa = new Integer[n];
7
        int[] rank = new int[n];
8
        int[] tmp = new int[n];
9
        for (int i = 0; i < n; i++) { sa[i] = i; rank[i] = s.charAt(i); }
10
        for (int k = 1; ; k <<= 1) {
11
            final int kk = k;
12
            final int[] r = rank;
13
            // Prefix-doubling: sort suffixes by their (rank, next-rank) pair, doubling
14
            // the compared length each round.
15
            Arrays.sort(sa, (a, b) -> {
16
                if (r[a] != r[b]) return Integer.compare(r[a], r[b]);
17
                int ra = a + kk < n ? r[a + kk] : -1;
18
                int rb = b + kk < n ? r[b + kk] : -1;
19
                return Integer.compare(ra, rb);
20
            });
21
            tmp[sa[0]] = 0;
22
            for (int i = 1; i < n; i++) {
23
                int prev = sa[i - 1], cur = sa[i];
24
                int pra = prev + kk < n ? r[prev + kk] : -1;
25
                int cra = cur + kk < n ? r[cur + kk] : -1;
26
                boolean same = r[prev] == r[cur] && pra == cra;
27
                tmp[cur] = tmp[prev] + (same ? 0 : 1);
28
            }
29
            System.arraycopy(tmp, 0, rank, 0, n);
30
            // All ranks distinct → suffixes are fully ordered, stop doubling.
31
            if (rank[sa[n - 1]] == n - 1) break;
32
        }
33
        int[] out = new int[n];
34
        for (int i = 0; i < n; i++) out[i] = sa[i];
35
        return out;
36
    }
37
 
38
    public int[] kasaiLcp(String s, int[] sa) {
39
        int n = s.length();
40
        int[] rank = new int[n];
41
        for (int i = 0; i < n; i++) rank[sa[i]] = i;
42
        int[] lcp = new int[n];
43
        int h = 0;
44
        for (int i = 0; i < n; i++) {
45
            if (rank[i] > 0) {
46
                int j = sa[rank[i] - 1];
47
                // Kasai extends the LCP; h carries over and drops by at most 1, giving
48
                // amortized O(n).
49
                while (i + h < n && j + h < n && s.charAt(i + h) == s.charAt(j + h)) h++;
50
                lcp[rank[i]] = h;
51
                if (h > 0) h--;
52
            } else {
53
                h = 0;
54
            }
55
        }
56
        return lcp;
57
    }
58
 
59
    public long countDistinct(String s) {
60
        int n = s.length();
61
        if (n == 0) return 0;
62
        int[] sa = suffixArray(s);
63
        int[] lcp = kasaiLcp(s, sa);
64
        // Gross substring count; long avoids overflow at ~5×10⁹.
65
        long total = (long) n * (n + 1) / 2;
66
        // Subtract every shared-prefix length — the formula distinct = n(n+1)/2 − ΣLCP.
67
        for (int v : lcp) total -= v;
68
        return total;
69
    }
70
 
71
    public static void main(String[] args) {
72
        System.out.println(new DistinctSubstrings().countDistinct("abab"));
73
    }
74
}

Yellow row = the algorithm's core logic. Amber `//` lines above it = what you'd say out loud.74 lines

D · Why it works and complexityO(n log n) timeO(n) spaceOpen the invariant and proofExplore the proof

E · Edge cases and pitfalls7s = "aaa" — SA = [2,1,0]; LCP = [0,1,2]; 6 − 3 = 3 distinct.Explore edge cases

Edge cases handled

s = "aaa"SA = [2,1,0]; LCP = [0,1,2]; 6 − 3 = 3 distinct.
s = "a"n=1, gross = 1, ΣLCP = 0 → 1.
all distinct chars "abc"ΣLCP = 0 → n(n+1)/2 = 6, every substring unique.

Pitfalls

Taking LCP between non-adjacent suffixes — only adjacent sorted pairs are correct.
Using a 32-bit accumulator for n(n+1)/2 — overflows for large n.
Computing rank from SA incorrectly in Kasai — rank[sa[i]] = i, not the reverse.
Forgetting that the first sorted suffix contributes its full length (LCP[0] = 0).

Practice

Try the solution yourself

Edit the optimal implementation, test another input, and observe the result.

Editable code previewimport java.util.Arrays; public class DistinctSubstrings { public int[] suffixArray(String s) { int n = s.length();Explore the playground

Try it — Java· run a complete program; method snippets need a driver

import java.util.Arrays;

public static void main(String[] args) {
        System.out.println(new DistinctSubstrings().countDistinct("abab"));
    }
}

Avoid mistakes

Recognize the interview traps

Understand why common attempts fail before reviewing the corrected implementation.

Stopping at the hash-set baseline

It enumerates all n²/2 substrings in both time and memory. For n = 10⁵ that is 10¹⁰ entries — it will not finish or fit. The interviewer expects the suffix-array reduction.

Explore the code comparison

Don't write this

seen = {s[i:j] for i in range(n) for j in range(i + 1, n + 1)}
return len(seen)   # O(n^2) time AND memory

Write this instead

sa = suffix_array(s)
lcp = kasai_lcp(s, sa)
return n * (n + 1) // 2 - sum(lcp)

Wrong rank inversion in Kasai

Kasai needs rank[i] = position of suffix i in SA. Writing sa[rank[i]] or inverting the assignment gives garbage LCPs.

Explore the code comparison

Don't write this

for (int i = 0; i < n; i++) rank[i] = sa[i]; // WRONG direction

Write this instead

for (int i = 0; i < n; i++) rank[sa[i]] = i; // rank is the inverse of SA

32-bit overflow on the gross count

n(n+1)/2 reaches ~5×10⁹ at n = 10⁵, past the 32-bit limit, so the subtraction underflows into a wrong (often negative) answer.

Explore the code comparison

Don't write this

int total = n * (n + 1) / 2; // overflows

Write this instead

long total = (long) n * (n + 1) / 2;

Revise

Carry the pattern into the interview

Quick interview revision

Pattern to remember

Suffix array + LCP: total substrings minus shared prefixes

Code pattern to memorize

distinct = n*(n+1)/2 - sum(LCP[i] for i in 1..n-1)
  where SA = sorted suffixes, LCP[i] = longest common prefix of SA[i] and SA[i-1]

Rules to remember

1Every substring is a prefix of some suffix — that reframing is the whole reason suffixes show up.
2Sort the suffixes; adjacent sorted suffixes share the most prefix, so LCP[i] counts exactly the duplicate substrings to subtract.
3Total substrings with duplicates is n(n+1)/2; distinct = that minus Σ LCP.
4The O(n²) hashing baseline stores every substring's hash in a set — correct, but O(n²) time and space, and risks collisions without verification.
5Use a separator-free input here; suffix arrays don't need one, unlike the Z/KMP concatenation trick.

Use this pattern when

Counting unique substrings, or unique substrings of a given length
Any problem reducible to 'distinct prefixes of suffixes'
Longest repeated substring, longest common substring of two strings
When you already need a suffix array/automaton for other queries

Choose another pattern when

n is tiny (≤ a few thousand) and you just need a quick answer → the hashing set is simpler to write
You need online/streaming updates → suffix automaton incremental construction
Only counting occurrences of one fixed pattern → KMP/Z, not a full suffix structure
Memory is extremely tight → suffix array uses O(n) ints; a hash set of substrings is far worse

Interview takeaway

Two reframings carry the whole problem: substrings are prefixes of suffixes, and sorting suffixes makes duplicate prefixes adjacent. The LCP array then turns 'count distinct' into one subtraction.

Continue

Transfer the pattern to another problem

Use a direct variation or pattern sibling to prove the idea is reusable.

Practice queueDirect variations and pattern siblings

Direct follow-ups

Longest Repeated Substring
Coming soon
The maximum value in the LCP array is the length of the longest substring that appears at least twice.
Longest Common Substring of Two Strings
Coming soon
Concatenate with a separator, build SA+LCP, take the max LCP between suffixes originating from different strings.
Count Distinct Substrings of Each Length
Coming soon
Use the LCP array bucketed by length, or a suffix automaton's per-state contributions.
Distinct Substrings via Suffix Automaton (O(n))
Coming soon
Sum len(state) − len(link(state)) over all states for a true linear-time count.

←

Strong Password

Continue · Next problem

Lexicographic Rank of a String