其实应该有感觉了。substring求最值的题(length of longest repeating substring), 不是two pointers就是dfs或者dp.

  • HashMap,HashSet都用不上，排除two pointers
  • repeating，也就是至少找2个，并不是扫一遍能递归的东西，dfs不行
  • dp: 2个substring的特征，往后面扫要纪录之前扫到的index所能达到的longest repeating substring, 适合二维dp；
  • dp什么作为之前就纪录好的东西？就是longest repeating substring的长度。
  • dp: index作为substring结尾的index.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public int longestRepeatingSubstring(String S) {
        int n = S.length(), res = 0;
        int[][] f = new int[n+1][n+1];
        
        for (int i = 1; i <= n; ++i) {
            for (int j = i + 1; j <= n; ++j) {
                if (S.charAt(i - 1) == S.charAt(j - 1)) {
                    f[i][j] = f[i-1][j-1] + 1;
                    res = Math.max(res, f[i][j]);
                }
            }
        }
        
        return res;
    }