# 1062. Longest Repeating Substring

## 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 <= 2000
• s consists of lowercase English letters.

## Solutions

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

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

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


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