滑动窗口
解题思路
看到这个题目时，可能会想着如何将某一序列里的一些元素替换成相同元素，然后再求得窗口长度，这样想会掉入陷阱，考虑的情况特别多；
解题思路和其他的滑动窗口一样，只是这个收缩左侧窗口的条件变成了
maxSame + k < right - left + 1;
- 说明窗口内的元素数量大于了 最大相同元素个数 + k 的总和；
- 此时需要收缩左侧窗口，求出
maxSame + k === right - left + 1
复杂度
-
时间复杂度：
O(N) -
空间复杂度：
O(1)
代码实现
var characterReplacement = function (s, k) {
// 1. 定义 hash 数组
const hash = new Array(26).fill(0);
const asset = 'A'.charCodeAt(0); // 偏移量
let maxSame = 0;
let len = s.length;
let left = 0;
let right = 0;
while (right < len) {
// 2. 增大窗口大小
const inx = s.charCodeAt(right) - asset;
hash[inx]++;
maxSame = Math.max(maxSame, hash[inx]);
//不符合情况时，缩小窗口
if (maxSame + k < right - left + 1) {
hash[s.charCodeAt(left) - asset]--;
left++;
}
right++;
}
return right - left;
};
打赏作者
您的打赏是我前进的动力
微信
支付宝
leetcode🧑💻 567. 字符串的排列
上一篇
评论
