题目链接
第一次尝试
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)的数量，否则就是不合规的，因为它应该在处理之后的子问题才考虑。
- 关于窗口收集了多少种类这个问题，我最开始是想找一个哈希表，之类的结构来判断这个窗口已经存了几种字符了，其实没必要，如果有新的种类进入窗口，说明它的数量初始为0,一加完变成了一，这样就说明它是一个新的类型，就要给
collect进行增加。
cnts[s[r]]++;
if (cnts[s[r]] == 1) {
collect++;
}
- 关于窗口合规的种类，还要一个变量
satisfy来确定当前窗口符合要求的字符的个数，一旦collect == satisfy就说明，我们当前require种字符出现次数都满足了大于等于k的要求了，那么就可以更新答案了。思想和1一样，一个字符加完了之后刚好等于k，不就说明，我们多了一种符合要求的字符吗？所以令satisfy增加
if (cnts[s[r]] == k) {
satisfy++;
}
- 如果超过了require的情况
那么就要考虑缩减窗口，同时要判断有没有导致collct和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);
}