1062. Longest Repeating Substring - Solution

The problem

Given a string s, return the length of the longest repeating substrings. If no repeating substring exists, return 0.

Example 1:

Input: s = "abcd"
Output: 0
Explanation: There is no repeating substring.

Example 2:

Input: s = "abbaba"
Output: 2
Explanation: The longest repeating substrings are "ab" and "ba", each of which occurs twice.

Example 3:

Input: s = "aabcaabdaab"
Output: 3
Explanation: The longest repeating substring is "aab", which occurs 3 times.

Constraints:

1 <= s.length <= 2000
s consists of lowercase English letters.

Approach overview

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.

Solution

We define f[i][j] to represent the length of the longest repeating substring ending with s[i] and s[j]. Initially, f[i][j]=0.

We enumerate i in the range [1, n) and enumerate j in the range [0, i). If s[i]=s[j], then we have:

$f[i][j]= \begin{cases} f[i-1][j-1]+1, & j>0 \ 1, & j=0 \end{cases}

The answer is the maximum value of all f[i][j].

The time complexity is O(n^2), and the space complexity is O(n^2). Where n is the length of the string s$.

Similar problems:

1044. Longest Duplicate Substring 🔒

Python

class Solution:
    def longestRepeatingSubstring(self, s: str) -> int:
        n = len(s)
        f = [[0] * n for _ in range(n)]
        ans = 0
        for i in range(1, n):
            for j in range(i):
                if s[i] == s[j]:
                    f[i][j] = 1 + (f[i - 1][j - 1] if j else 0)
                    ans = max(ans, f[i][j])
        return ans

Java

class Solution {
    public int longestRepeatingSubstring(String s) {
        int n = s.length();
        int[][] f = new int[n][n];
        int ans = 0;
        for (int i = 1; i < n; ++i) {
            for (int j = 0; j < i; ++j) {
                if (s.charAt(i) == s.charAt(j)) {
                    f[i][j] = 1 + (j > 0 ? f[i - 1][j - 1] : 0);
                    ans = Math.max(ans, f[i][j]);
                }
            }
        }
        return ans;
    }
}

C++

class Solution {
public:
    int longestRepeatingSubstring(string s) {
        int n = s.length();
        int f[n][n];
        memset(f, 0, sizeof(f));
        int ans = 0;
        for (int i = 1; i < n; ++i) {
            for (int j = 0; j < i; ++j) {
                if (s[i] == s[j]) {
                    f[i][j] = 1 + (j > 0 ? f[i - 1][j - 1] : 0);
                    ans = max(ans, f[i][j]);
                }
            }
        }
        return ans;
    }
};

TypeScript

function longestRepeatingSubstring(s: string): number {
    const n = s.length;
    const f: number[][] = Array.from({ length: n }).map(() => Array(n).fill(0));
    let ans = 0;
    for (let i = 1; i < n; ++i) {
        for (let j = 0; j < i; ++j) {
            if (s[i] === s[j]) {
                f[i][j] = 1 + (f[i - 1][j - 1] || 0);
                ans = Math.max(ans, f[i][j]);
            }
        }
    }
    return ans;
}

func longestRepeatingSubstring(s string) (ans int) {
	n := len(s)
	f := make([][]int, n)
	for i := range f {
		f[i] = make([]int, n)
	}
	for i := 1; i < n; i++ {
		for j := 0; j < i; j++ {
			if s[i] == s[j] {
				if j > 0 {
					f[i][j] = f[i-1][j-1]
				}
				f[i][j]++
				ans = max(ans, f[i][j])
			}
		}
	}
	return
}

Rust

impl Solution {
    pub fn longest_repeating_substring(s: String) -> i32 {
        let n = s.len();
        let mut f = vec![vec![0; n]; n];
        let mut ans = 0;
        let s = s.as_bytes();

        for i in 1..n {
            for j in 0..i {
                if s[i] == s[j] {
                    f[i][j] = if j > 0 { f[i - 1][j - 1] + 1 } else { 1 };
                    ans = ans.max(f[i][j]);
                }
            }
        }
        ans
    }
}

Try this approach in the editor

Complexity analysis

Approach	Time	Space	When to Use
Brute Force Substring Comparison	O(n^3)	O(1)	Good for understanding the problem or very small inputs
Dynamic Programming	O(n^2)	O(n^2)	Most straightforward implementation for interviews
Binary Search + Rolling Hash	O(n log n)	O(n)	Efficient solution for large strings
Suffix Array + LCP	O(n log n)	O(n)	Best for advanced string processing or competitive programming

Frequently asked questions

Is Longest Repeating Substring easy or hard?

Longest Repeating Substring is generally considered a medium-level problem. The DP solution is straightforward once you recognize the longest common substring pattern, but optimized solutions using rolling hash or suffix arrays require stronger knowledge of string algorithms.

How to solve Longest Repeating Substring in O(n log n)?

Use binary search on the substring length combined with a rolling hash (Rabin–Karp). For each candidate length L, compute hashes for all substrings of length L and store them in a hash set. If a duplicate hash appears, a repeating substring exists. Binary search over the length range gives O(n log n) time.

What is the best approach for Longest Repeating Substring?

The most practical interview approach is dynamic programming with O(n^2) time and O(n^2) space. It compares all suffix pairs and tracks the longest common suffix length using a DP table. For better theoretical performance, binary search combined with rolling hash reduces the complexity to O(n log n).

What data structure is used in Longest Repeating Substring?

Common techniques rely on dynamic programming tables, hash sets for rolling hash comparisons, and advanced structures such as suffix arrays or LCP arrays. The choice depends on the desired time complexity and implementation difficulty.

What is the time complexity of Longest Repeating Substring?

The brute force method runs in O(n^3) time. A dynamic programming solution improves this to O(n^2) time with O(n^2) space. More advanced approaches such as binary search with rolling hash or suffix arrays can solve it in O(n log n) time.

Longest Repeating Substring Python or Java solution approach?

Most Python and Java solutions use a dynamic programming table where dp[i][j] stores the length of the common suffix ending at indices i and j. If characters match, extend the previous result with dp[i-1][j-1] + 1. The maximum value in the table is the answer, giving O(n^2) time complexity.

Is Longest Repeating Substring asked at Google, Amazon, or Meta?

Variants of longest repeating substring and longest duplicate substring problems appear in interviews at companies like Google, Amazon, and Meta. They are commonly used to test knowledge of string algorithms, hashing techniques, and suffix-based data structures.

Longest Repeating Substring solution and explanation

The problem

Approach overview

Solution

Complexity analysis

Frequently asked questions

Comments

Longest Repeating Substring solution and explanation

The problem

Approach overview

Solution

Complexity analysis

Frequently asked questions

Comments

Related problems