给定字符串s和整数k,找出s中的最长子串,要求子串中的每一字符出现的次数都不少于k,返回这一子串的长度。
思路有点难理解
题目中先定了字符串中只有26个小写字母,满足题意的子串中不同字母数在1-26范围内,从1-26枚举,对于每个cnt,维护窗口指针start和end,不断更新start和end,保持窗口内不同字符数不超过cnt,用一个大小为26的数组来记录窗口内每个字母的出现次数。
更新start和end方式,让end不断加1更新,start的更新看情况:
判断end是不是一个全新的字符,是的情况下让uniquecnt加1,这个时候可能uniquecnt超过了指定的cnt,需要将start右移直到 uniquecnt 不超过 cnt,每次更新好end和start后还需要判断窗口内每个字符串是否满足条件,若是应该尝试更新 res
- 时间复杂度 O(26 * n + 26^2),空间复杂度O(26)
- Runtime: 134 ms, faster than 45.31%
- Memory Usage: 41 MB, less than 75.00%
/**
* @param {string} s
* @param {number} k
* @return {number}
*/
var longestSubstring = function(s, k) {
let res = 0;
const len = s.length;
for (let i = 1; i <= 26; i++) {
let left = 0;
let right = 0;
let unique = 0;
const count = new Array(26).fill(0);
while (right < len) {
if (count[s[right].charCodeAt() - 97]++ === 0) {
unique++;
}
while (unique > i) {
if (--count[s[left++].charCodeAt() - 97] === 0) {
unique--;
}
}
let valid = true;
for (let item of count) {
if (item > 0 && item < k) {
valid = false;
break;
}
}
if (valid) {
res = Math.max(res, right - left + 1);
}
right++;
}
}
return res;
};