[Leetcode 1062] Longest Repeating Substring

原题说明

Given a string S, find out the length of the longest repeating substring(s). Return 0 if no repeating substring exists.

 

Example 1:

Input: “abcd”
Output: 0
Explanation: There is no repeating substring.

Example 2:

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

Example 3:

Input: “aabcaabdaab”
Output: 3
Explanation: The longest repeating substring is “aab”, which occurs 3 times.

Example 4:

Input: “aaaaa”
Output: 4
Explanation: The longest repeating substring is “aaaa”, which occurs twice.

 

Constraints:

• The string S consists of only lowercase English letters from ‘a’ - ‘z’.
• 1 <= S.length <= 1500

解题思路

这题我们采用动态规划的方法。
我们先定义dp[i][j]为分别以第i个字符和第j个字符结尾的substring有相同共同后缀的最大长度。因此，我们也要求i>j。
我们注意到，当S[i] != S[j], 那么dp[i][j] = 0， 否则dp[i][j] = dp[i-1][j-1] + 1。这就是我们的状态转移方程。

dp[i][j] = dp[i-1][j-1] + 1 ----------- S[i] == S[j]
dp[i][j] = 0 ----------- S[i] != S[j]

我们更新dp[i][j]的最大值，就可以得到最后的答案。

示例代码 (cpp)

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

示例代码 (java)

class Solution {
    public int longestRepeatingSubstring(String S) {
        int res = 0;
        int n = S.length();
        int[] dp = new int[n + 1];
        
        for (int i = 1; i <= n; i++) {
		   // Need start from i - 1 to use values from last iteration
            for (int j = i - 1; j >= 1; j--) {
                if (S.charAt(i - 1) == S.charAt(j - 1)) {
                    dp[j] = dp[j - 1] + 1;
                } else {
                    dp[j] = 0;
                }
                
                res = Math.max(res, dp[j]);
            }
        }
        
        return res;
    }
}

示例代码 (python)

class Solution:
    def longestRepeatingSubstring(self, S: str) -> int:
        ans = 0
        for i in range(1, len(S)):
            if ans >= len(S)-i: 
                break 
                
            tmp = 0
            for x, y in zip(S[i:],S[:-i]):
                if x == y:
                    tmp += 1 
                    ans = max(ans, tmp)
                else:
                    tmp = 0 
            
        return ans

复杂度分析

N是字符串的长度。
时间复杂度: O(N^2)
空间复杂度: O(N^2)

视频讲解

我们在Youtube上更新了视频讲解，欢迎关注！