Articles
Suffix Array Interview Questions: Repeated Substrings and LCP Reasoning
Suffix array interview questions with worked LCP intervals, repeated and non-overlapping substrings, distinct counts, and realistic construction costs.
A suffix array interview becomes interesting when the interviewer changes “find a repeated substring” to “find one that occurs three times” or “find two occurrences that do not overlap.” The same sorted suffixes remain useful, but the answer is no longer simply the largest adjacent LCP value.
A suffix array stores starting positions of a string's suffixes in lexicographic order. An LCP array records common-prefix lengths between neighboring suffixes under a stated indexing convention. Together they turn shared substrings into contiguous intervals of suffix ranks.
Evidence boundary: Princeton's teaching implementation and the original LCP research support the underlying methods. The tables, counterexamples, and verification exercises below are original derivations. We make no claim about which employers ask suffix arrays or how frequently.
Begin with Find longest duplicated substring, then change the occurrence and overlap constraints before deciding whether the same solution still works.
State the suffix array contract before coding
Specify the input representation, ordering, and output. Are positions byte offsets, Unicode code-point indexes, or language-specific code-unit indexes? Is matching case-sensitive? Does an empty result mean no repeated nonempty substring?
For the worked examples, use ASCII strings, zero-based starting positions, and no added terminal sentinel. Define LCP[0] = 0; for rank r > 0, LCP[r] compares suffixes at ranks r-1 and r. A different convention can be correct, but mixing conventions breaks interval calculations.
The Princeton suffix-array reference presents sorted suffixes and repeated-substring applications. Its significance is the shared-prefix structure, not a claim that copying every suffix is efficient in every language. Princeton: Suffix Arrays
If a construction uses a sentinel, explain why it is unique and how it orders relative to the alphabet. Remove sentinel-containing answers before returning an application substring. Do not quietly append a character that might already occur in the input.
Also clarify ties. If several longest repeats exist, the contract may require any answer, the lexicographically smallest answer, or a particular occurrence. Choose a deterministic rule only after you know which result the caller expects.
Derive a complete suffix and LCP table
Use the original worked string abracadabra, of length 11. Its sorted suffixes and previous-neighbor LCP values are:
| Rank | Start | Suffix | LCP with previous |
|---|---|---|---|
| 0 | 10 | a | 0 |
| 1 | 7 | abra | 1 |
| 2 | 0 | abracadabra | 4 |
| 3 | 3 | acadabra | 1 |
| 4 | 5 | adabra | 1 |
| 5 | 8 | bra | 0 |
| 6 | 1 | bracadabra | 3 |
| 7 | 4 | cadabra | 0 |
| 8 | 6 | dabra | 0 |
| 9 | 9 | ra | 0 |
| 10 | 2 | racadabra | 2 |
The maximum LCP is four, between starts seven and zero. Their shared prefix is abra, which occurs twice. The next characters either differ or one suffix ends; the shared prefix cannot extend further.
Check the table manually before implementing a faster constructor. Every start index from zero through ten must appear once. Suffixes must be sorted under the declared ordering. Each LCP must be no longer than either suffix and must describe their actual prefix.
Those checks catch a corrupted permutation, a sorting error, and an off-by-one LCP error separately. A final answer that happens to be abra is insufficient evidence that every intermediate array is correct.
Why are adjacent suffixes sufficient for two occurrences?
Suffixes beginning with a particular prefix form a contiguous lexicographic interval. If two suffixes share a prefix of length L, every suffix between them also begins with that prefix. Some neighboring pair inside the interval therefore has an LCP of at least L.
That argument explains why scanning adjacent pairs can find the longest repeated substring when overlap is allowed. It avoids comparing every pair of suffixes, but does not make sorting or LCP construction free.
For ranks p < q, the common-prefix length of the endpoint suffixes equals the minimum of LCP[p+1] through LCP[q]. A low LCP inside the interval prevents a longer prefix from being shared by both endpoints.
On the worked table, the suffixes at ranks one and two share four characters. Ranks one through four share only one, because the minimum across the connecting LCP values is one. An interval query uses the minimum, not the maximum.
If the interviewer asks many arbitrary suffix-pair queries, this becomes a range-minimum problem over LCP after building an inverse rank array. State preprocessing and query costs for the chosen range-minimum structure instead of attributing every performance gain to the suffix array itself.
How do you find a substring occurring at least k times?
A prefix present in at least k suffixes has an interval containing a window of k consecutive ranks. The shared-prefix length for that window is the minimum of its k-minus-one connecting LCP values.
For k equal to three, consider starts ten, seven, and zero in the first three ranks of abracadabra. The connecting LCP values are one and four, so the shared prefix has length one. It is a. A large pairwise repeat does not establish three occurrences.
Slide a window of k suffixes and maximize that window minimum. A monotonic deque can maintain the relevant LCP minimum in linear time after the arrays exist. Explain which indices enter and expire; a window of k suffixes is a window of k-minus-one LCP edges.
Handle k equal to one separately: the whole input is a longest substring with at least one occurrence. If k exceeds the number of suffixes, no nonempty answer exists. Define the empty-input behavior rather than forcing a window into an invalid array range.
Occurrence counts here refer to starting positions and allow overlap. A request for k non-overlapping occurrences needs a different feasibility test. Do not silently carry the two-occurrence distance criterion into that more demanding variant.
What changes when overlapping occurrences are forbidden?
Consider aaaaa. With overlap allowed, aaaa occurs at starts zero and one. Its adjacent LCP is four. Those two length-four occurrences overlap heavily.
If two occurrences must not overlap, aa works at starts zero and two. No length-three substring can occur twice without overlap in a five-character input. Therefore the maximum-LCP answer is wrong for the changed contract.
For a candidate length L, partition suffix ranks into connected groups whose internal LCP edges are at least L. Within each group, track the minimum and maximum starting positions. Two non-overlapping occurrences exist if their difference is at least L.
This position-extreme test works for two occurrences because the greatest distance between any pair is the maximum start minus the minimum start. It is not enough to prove k separated occurrences; for that variant, gather positions and check spacing appropriately.
Feasibility for two occurrences is monotone in L: if a length-L repeated substring has separated occurrences, a shorter prefix at those starts also works. Binary search L with an O(n) group scan gives O(n log n) checking time after suffix and LCP construction.
Count distinct substrings using the same arrays
A suffix starting at index i contributes n-i nonempty prefixes. When suffixes are processed in sorted order, the first LCP[r] prefixes of the current suffix have already appeared among earlier suffixes.
Thus the number of distinct nonempty substrings is n(n+1)/2 - sum(LCP). For abracadabra, the total before removing duplicates is 66 and the LCP sum is 13. The result is 53.
This is an original numerical check using the stated table. It is not a count of distinct subsequences, which can skip characters, or a count of substring occurrences, which retains repeated positions.
Use an integer type large enough for the triangular count. A constructor that handles a large input can still produce an overflow in a small result accumulator. State the bound rather than assuming an index-sized integer is sufficient.
A useful follow-up asks why subtracting only the previous neighbor is enough. The previous suffix captures the longest prefix already represented among earlier suffixes; the interval property provides the reasoning. Do not subtract every pairwise LCP, which would remove shared prefixes repeatedly.
Build LCP without repeatedly restarting comparisons
The original Kasai and colleagues paper establishes a linear-time LCP construction once the suffix ordering is known. The algorithm uses inverse ranks and carries a common-prefix length between nearby starting positions. Linear-Time Longest-Common-Prefix Computation
The important interview explanation is amortization. Advancing one character in the text means the carried prefix can shrink by at most one before further comparison, under the algorithm's rank relationships. Across the scan, the carried length does not restart from zero for every pair.
Be explicit about the first-ranked suffix. It has no previous neighbor under our convention, so its LCP is zero and the carried value must be handled consistently. Bound both compared positions before reading characters.
This linear bound concerns LCP construction. It does not retroactively make a naive suffix sort linear. Keep the costs of construction, LCP, and the application's query separate.
Choose construction costs you can defend
Sorting copied suffix strings is a convenient tiny-input baseline. It can allocate quadratic total character storage, and character-by-character comparisons can be expensive on repetitive inputs. The exact behavior depends on the language's string representation.
Prefix doubling instead ranks pairs of length-k blocks, then doubles k. Sorting those pairs with a comparison sort over logarithmically many rounds commonly gives O(n log-squared n) time. Rank-aware counting or radix sorting can reduce that construction bound to O(n log n).
These are implementation-specific bounds, not promises that every suffix-array constructor behaves the same way. Princeton's SuffixArray implementation is a useful concrete reference to inspect alongside your chosen approach.
For one pattern searched once, a suffix array may be unnecessary. For repeated queries over static text, preprocessing can make sense. If the text changes continually, ask whether rebuilding the index is acceptable; the static-array argument does not automatically solve a dynamic indexing contract.
Practice the query contract, not only construction
Some call for a different structure under their constraints; explaining that choice is part of the practice, not a claim that every row should use a suffix array.
| Practice question | What to explain |
|---|---|
| Find longest duplicated substring | State overlap rules before maximizing a repeated substring. |
| Find the Lexicographically Maximum Suffix | Compare suffix ordering with a single maximum query. |
| Build a Dynamic Exact-Suffix Search Index | Distinguish a static suffix array from a mutable index. |
| Find shortest unique substring per word | Explain uniqueness using neighboring suffix evidence. |
| Most Frequent Substring Under Distinct-Letter and Length Limits | Separate frequency and character constraints from length. |
Start with Find longest duplicated substring and write your assumptions before answering. Compare your explanation against the specific invariants above, then use a second question to test whether the reasoning transfers to a different constraint.