Suffix Array Problems
5 Suffix Array LeetCode problems · Browse tasks by difficulty and choose your next practice problem.
Learn the coding interview patterns behind these problems.
Find repeated text by sorting suffix positions
A suffix array stores the starting positions of a string's suffixes in lexicographic order. Similar prefixes become neighbors, so the longest common prefix of adjacent suffixes can reveal repeated substrings. Store indices rather than copying every suffix; the copied strings together can occupy quadratic space.
When to use it
Consider a suffix array when many substring comparisons or repeated-substring queries share the same text. Longest Duplicate Substring is a direct application. Multi-sequence tasks need separators that cannot occur in the input and checks that matches do not cross sequence boundaries.
Worked example
Text: banana, with zero-based positions 0 through 5.
- Sorted suffixes are a, ana, anana, banana, na, nana. Their start positions are [5, 3, 1, 0, 4, 2].
- Adjacent longest-common-prefix lengths are [1, 3, 0, 0, 2]. The largest length is 3, between ana and anana.
- Read three characters at positions 3 and 1 in the original text; both produce ana.
The longest duplicated substring is ana. Its two occurrences overlap, which is allowed for this example.
Time and space
Prefix doubling with comparison sorting of rank pairs takes O(n log² n) time and O(n) working space; radix sorting the rank pairs can reduce construction to O(n log n). Given a suffix array and inverse ranks, Kasai's algorithm computes all adjacent LCP lengths in O(n) time.
Mistakes to check
- Sorting suffix indices with full substring comparisons can repeatedly scan long common prefixes; it does not have the same cost as sorting constant-size rank pairs.
- State whether overlapping matches count. A longest repeated substring and a longest non-overlapping repeat are different tasks.
- Define the unit of indexing for non-ASCII text. Bytes, UTF-16 code units, and Unicode code points can produce different positions and ordering.
Further reading: Princeton Algorithms: suffix arrays and longest common prefixes
Guide reviewed .