Longest Repeating Substring - Solution & Explanation

Problem Overview: Given a string s, return the length of the longest substring that appears at least twice in the string. The repeated substrings can overlap, but their positions must be different.

Approach 1: Brute Force Enumeration (O(n^3) time, O(1) space)

Generate every possible substring and check whether it appears again later in the string. For each starting index, expand the substring and compare it with the remaining suffix using direct string comparison. This involves up to O(n^2) substrings and each comparison can take O(n) time, leading to O(n^3) total complexity. The approach is simple and useful for understanding the problem, but it quickly becomes impractical for larger inputs.

Approach 2: Dynamic Programming (O(n^2) time, O(n^2) space)

This method compares all suffix pairs using a DP table. Define dp[i][j] as the length of the longest common suffix of substrings ending at indices i and j. If s[i] == s[j], then dp[i][j] = dp[i-1][j-1] + 1. Only consider cases where i < j to ensure the substrings come from different positions. The maximum value in the table gives the length of the longest repeating substring. This technique is closely related to longest common substring problems and is a natural application of dynamic programming. It runs in O(n^2) time with O(n^2) memory.

Approach 3: Binary Search + Rolling Hash (O(n log n) time, O(n) space)

Instead of testing every substring length, binary search the answer. For a candidate length L, check whether any substring of length L appears more than once. Use a rolling hash (Rabin–Karp) to compute hashes for all substrings of length L in O(n) time and store them in a hash set. If a duplicate hash appears, a repeating substring exists. Binary search over the range [1, n], giving O(n log n) total time and O(n) space. This technique combines binary search with rolling hash for efficient substring comparison.

Approach 4: Suffix Array / Suffix LCP (O(n log n) time, O(n) space)

Construct a suffix array of the string and compute the LCP (Longest Common Prefix) array between adjacent suffixes. The maximum value in the LCP array directly represents the longest repeating substring. This approach is theoretically clean and widely used in advanced string processing systems, though it is more complex to implement during interviews.

Recommended for interviews: The dynamic programming solution is the most straightforward to derive and implement under time pressure. It demonstrates understanding of substring comparisons and DP transitions. Strong candidates often mention the binary search + rolling hash optimization, which reduces the complexity to O(n log n) and shows deeper familiarity with string algorithms.