1062. Longest Repeating Substring

實際上這題跟 718 差不多, 差別在於因為要找的是 repeat sunstring, 所以我們立刻可以想到一樣用兩個字串來比較看看, 這樣就跟 718 題目變的一樣了, 要找的是 longest common substring(subarray)

但稍微有點不一樣, 也就是兩個字串在同一個位置上不能視為 common (看題目的意思可以了解

DP

T: O(n^2)

S: O(n^2)

class Solution {
    public int longestRepeatingSubstring(String s) {
        int n = s.length();
        s = "#" + s;
        int[][] dp = new int[n+1][n+1];
        dp[0][0] = 0;
        
        int max = 0; // 最少長度是 0
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= n; j++) {
                if (i != j && s.charAt(i) == s.charAt(j)) {
                    dp[i][j] = dp[i-1][j-1] + 1;
                    max = Math.max(max, dp[i][j]);
                }
            }
        }
        return max;
    }
}

/*
seen s as two string to compare

xxx[xxxxi]
x[xxxxj]

dp[i][j]: string s1 with ending i and string s2 with ending j, has the common substring len

if (S[i] == S[j]) so 

if (S[i] == S[j]) dp[i][j] = dp[i-1][j-1] + 1;
*/