力扣395做题笔记

题目链接

力扣395

第一次尝试

class Solution {public int longestSubstring(String str, int k) {char[] s = str.toCharArray();int n = s.length;int[] cnts = new int[256];int ans = 0;for (int r = 0, l = 0; r < n; r ++) { cnts[s[r]]++;if (cnts[s[r]] >= k) { ans = Math.max(ans, r - l + 1);// l = r + 1;}}return ans;}
}

结果遇到这个样例：

输入
s ="ababacb" k =3输出
7
预期结果
0

题目强调的是该子串里面的每一种字符都要大于k，我的写法错误地理解为只要有一种大于k的子串就行了。

左神解法

这里利用了一点动态规划的思想，这个字符串都是小写的字符串。

那么就说明，最多有26种字符来组合一个字符串。那么我们从1分析到26,找出子串含有1~26种，每种符合的长度，然后比长短既可以了。
相当于就26种子问题，组合一起就是总问题了。

class Solution {public int longestSubstring(String str, int k) {char[]s = str.toCharArray();int[] cnts = new int[256];int n = s.length;int ans = 0;//collect 当前窗口收集到的字符种类数//satisfy 当前窗口满足条件的种类的数量for (int require = 1; require <= 26; require ++) { Arrays.fill(cnts, 0);for (int r = 0, l = 0, collect = 0, satisfy = 0; r < n; r ++) { cnts[s[r]]++;if (cnts[s[r]] == 1) { collect++;}if (cnts[s[r]] == k) { satisfy++;}//处理种数超过require的情况while (collect > require) {if (cnts[s[l]] == k) { satisfy --;}if (cnts[s[l]] == 1) { collect --;}cnts[s[l++]]--;}//合规，更新答案if (collect == satisfy) {ans = Math.max(ans, r - l + 1);}}}return ans;}
}

我们要看当前窗口收集了多少种类，要控制它不能超过当前处理的子问题(require)的数量，否则就是不合规的，因为它应该在处理之后的子问题才考虑。

1. 关于窗口收集了多少种类这个问题，我最开始是想找一个哈希表，之类的结构来判断这个窗口已经存了几种字符了，其实没必要，如果有新的种类进入窗口，说明它的数量初始为0,一加完变成了一，这样就说明它是一个新的类型，就要给collect进行增加。

                cnts[s[r]]++;if (cnts[s[r]] == 1) { collect++;}

2. 关于窗口合规的种类，还要一个变量satisfy来确定当前窗口符合要求的字符的个数，一旦collect == satisfy就说明，我们当前require种字符出现次数都满足了大于等于k的要求了，那么就可以更新答案了。思想和1一样，一个字符加完了之后刚好等于k，不就说明，我们多了一种符合要求的字符吗？所以令satisfy增加

                if (cnts[s[r]] == k) { satisfy++;}

3. 如果超过了require的情况
   那么就要考虑缩减窗口，同时要判断有没有导致collct和satisfy的变化。

              //处理种数超过require的情况while (collect > require) {if (cnts[s[l]] == k) { satisfy --;}if (cnts[s[l]] == 1) { collect --;}cnts[s[l++]]--;}

4. 最后更新返回答案即可

                if (collect == satisfy) {ans = Math.max(ans, r - l + 1);}