Description
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 <= 2000s consists of lowercase English letters.
Solutions
Solution 1: Dynamic Programming
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(n2), and the space complexity is O(n2). Where n is the length of the string s.
Similar problems:
PythonJavaC++GoTypeScriptRust
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(code-box)
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;
}
}(code-box)
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;
}
};(code-box)
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
}(code-box)
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;
}(code-box)
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
}
}(code-box)
