Welcome to Subscribe On Youtube
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 <= 2000sconsists 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 }