How Do You Solve the Longest Repeated Substring Problem?
Learn how to solve the longest repeated substring problem using suffix arrays and Kasai’s LCP algorithm for this interview question.
Expected Interview Answer
The longest repeated substring problem asks for the longest substring that occurs at least twice, possibly overlapping, in a given string, and the standard efficient solution builds a suffix array with an accompanying LCP (longest common prefix) array, then returns the maximum value in the LCP array since it directly measures shared prefixes between lexicographically adjacent suffixes.
A naive approach comparing all pairs of substrings is O(n²) to O(n³), which is far too slow for long strings. Building a suffix array sorts all n suffixes lexicographically in O(n log n) using techniques like prefix doubling, and computing the LCP array via Kasai's algorithm in O(n) then tells you, for each pair of adjacent suffixes in sorted order, how many leading characters they share. Because any repeated substring must be a common prefix of two suffixes, and lexicographically adjacent suffixes are the ones most likely to share the longest prefix, the maximum LCP value directly gives the longest repeated substring length, with its position recoverable from the suffix array. An equivalent and equally efficient alternative builds a suffix automaton and finds the state with the maximum len value among states that are not the clone of any other, since automaton states with multiple ending positions correspond to repeated substrings.
- Suffix array + LCP solves it in O(n log n) total
- Kasai's algorithm computes LCP in linear time after sorting
- Suffix automaton offers an O(n) alternative approach
- Both avoid the naive O(n²)+ pairwise substring comparison
AI Mentor Explanation
Finding the longest repeated substring is like a scout trying to find the longest identical shot-sequence a batter has played twice in a season, without comparing every possible sequence against every other pairwise. Instead, the scout lists every remaining “innings-from-this-ball-onward” fragment, sorts them alphabetically by shot description, and then only compares each fragment to its immediate neighbor in the sorted list, since identical or near-identical fragments naturally land next to each other once sorted. The longest shared beginning between any two neighboring fragments in that sorted list is the longest shot-sequence the batter has repeated. This sorted-neighbor trick turns an expensive pairwise comparison across the whole season into one sort plus one linear scan.
Step-by-Step Explanation
Step 1
Build the suffix array
Sort all n suffixes of the string lexicographically, in O(n log n) with prefix doubling.
Step 2
Compute the LCP array
Run Kasai's algorithm in O(n) to find the longest common prefix between each pair of adjacent suffixes in the sorted order.
Step 3
Scan for the maximum LCP value
The largest value in the LCP array is the length of the longest repeated substring.
Step 4
Recover the substring
Use the suffix array position at the max LCP index to extract the actual repeated substring from the original string.
What Interviewer Expects
- Rule out the naive O(n²) to O(n³) pairwise substring comparison approach
- Explain suffix array + LCP array as the standard O(n log n) solution
- Explain why adjacent suffixes in sorted order matter for LCP
- Mention the suffix automaton as an O(n) alternative
Common Mistakes
- Comparing every pair of substrings directly instead of using suffixes and sorting
- Forgetting the LCP is computed between adjacent sorted suffixes, not arbitrary pairs
- Confusing longest repeated substring with longest common substring of two different strings
- Not handling overlapping occurrences correctly
Best Answer (HR Friendly)
“The longest repeated substring problem asks for the longest chunk of text that shows up more than once in a string. The efficient way to solve it is to sort all the suffixes of the string, then look at how much consecutive sorted suffixes share at the start — the biggest overlap there is the answer, and it runs in about O(n log n) instead of comparing every pair of substrings directly.”
Code Example
def build_suffix_array(s):
n = len(s)
sa = list(range(n))
rank = [ord(c) for c in s]
tmp = [0] * n
k = 1
while k < n:
def key(i):
return (rank[i], rank[i + k] if i + k < n else -1)
sa.sort(key=key)
tmp[sa[0]] = 0
for i in range(1, n):
tmp[sa[i]] = tmp[sa[i - 1]] + (key(sa[i - 1]) < key(sa[i]))
rank = tmp[:]
if rank[sa[-1]] == n - 1:
break
k <<= 1
return sa
def kasai_lcp(s, sa):
n = len(s)
rank = [0] * n
for i, suf in enumerate(sa):
rank[suf] = i
lcp = [0] * n
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]] = h
if h > 0:
h -= 1
else:
h = 0
return lcp
def longest_repeated_substring(s):
sa = build_suffix_array(s)
lcp = kasai_lcp(s, sa)
max_len = max(lcp) if lcp else 0
idx = lcp.index(max_len) if max_len else -1
return s[sa[idx]:sa[idx] + max_len] if idx != -1 else ""Follow-up Questions
- How would you find the longest common substring between two different strings instead?
- How does Kasai's algorithm achieve O(n) after the suffix array is built?
- How would you handle finding all repeated substrings above a length threshold, not just the longest?
- How would a suffix automaton solve this same problem?
MCQ Practice
1. What does the maximum value in the LCP array represent?
The maximum LCP value across adjacent sorted suffixes equals the length of the longest substring that repeats in the string.
2. What is the time complexity of building a suffix array with prefix doubling followed by Kasai's LCP algorithm?
Prefix doubling sorts suffixes in O(n log n); Kasai's algorithm then computes the LCP array in O(n), so the total is O(n log n).
3. Why is a naive pairwise comparison of all substrings a poor approach for this problem?
Comparing every pair of substrings directly is at best O(n^2) and often O(n^3) with comparison cost, far slower than the O(n log n) suffix array approach.
Flash Cards
What two structures solve the longest repeated substring problem efficiently? — A suffix array combined with an LCP array (via Kasai’s algorithm).
What does the LCP array measure? — The length of the longest common prefix between each pair of lexicographically adjacent suffixes.
What is the overall time complexity of the suffix array + LCP approach? — O(n log n), dominated by suffix array construction.
Name an O(n) alternative data structure for this problem. — A suffix automaton, using the state with maximum len among non-clone states.