給定字符串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;
};