1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
    public int characterReplacement(String s, int k) {
        int left = 0, right = 0, maxCount = 0, maxLength = 0;
        int[] count = new int[26];
        while (right < s.length()) {
            // Include a new char
            count[s.charAt(right) - 'A'] += 1;
            maxCount = Math.max(maxCount, count[s.charAt(right) - 'A']);
            // If necessary, pop out a char
            // 什么时候pop, 什么时候push很重要
            if (right - left + 1 - maxCount > k) {
                count[s.charAt(left) - 'A'] -= 1;
                left += 1;
            }
            maxLength = Math.max(maxLength, right - left + 1);
            right += 1;
        }
        return maxLength;
    }
}

就是sliding window. right每次往右延伸一格. 然后更新新包含进来的那个char的频率. 之后获得当前window中频率最大的char是哪个, 然后看除了它以外的char的个数是否大于k, 如果是的话, 就需要把left往右移动一位, 从而让其他char的出现的个数小于k. 如果小于等于就不需要这步移动left的操作. 然后计算此时sliding window的size, 去和maxLength比较即可.

至于第11行的if还是while. left向右移动一位就一定会让maxCount以外的char的count小于k. 因为right是一个一个移动的. 开始一步或者几步肯定是maxCount以外的char的count小于等于k(即使k == 0, 我们在包含进第0个char的时候maxCount以外的char的count(0)也是小于等于k的). 我们在后续某一步可能会遇到maxCount以外的char的count大于k, 那么在这个循环的前一个循环maxCount以外的char的count是小于等于k的, 且这个maxCount比现在的maxCount是小于等于的关系. 我们此时right变大了1, 发现right - left + 1 - maxCount大于k. 这意味着此时的maxCount一定是等于上一次的maxCount, 如果比之前大, 那么就会抵消right的增加而不会让最后的结果大于k. 我们让left右移一位, 此时right - left + 1 - maxCount比之前少了1, 也就抵消了right的增加. 那么此时的right - left + 1 - maxCount就会小于k.

时间复杂度: O(n)
空间复杂度: O(1)

最新的感想和理解

sliding window能够work的前提就是我们right停止时能够排除以当前left的位置, right以及以后的位置与left框起来的区域都不可能构成最终答案的substring. 这点是需要证明的. 下面我们来说明.

我们初始化left为0, right为0, 然后让right开始走. 当走到一个位置发现sliding window里的除了拥有最大frequency的其他char的数目大于k的时候, 此时以left为start的substring最长满足题意的就是[left, right)框起来这个区间, 左闭右开. 为什么? 如果right继续移动, 假设之后window里的freq最大的char没有改变, 那不用说, 本来剩下的char的数目就大于K, 往后只可能剩下的越来越多, 最好情况也就是剩下的数目不变, freq最大的char的个数一直在增加, 因此不满足题意; 如果后面在某个时刻freq最大的char改变了, 此时我们来证明一下. 首先我们假设在之前right停止的位置, 最大freq char假设是‘a’, 个数为x个, 下一次将成为max freq char现在的count是y, 其余剩余的char个数为z个, 此时总个数为x + y + z个, 我们把总数记为S1. 此时有S1 - x > k. 那么到了某个时刻, 最大freq char换成比如说‘b’了, 假设‘a’增加了m1个, 此时count是x + m1, ‘b’增加了m2个变为了, 此时count是y + m2, 其余的char的总增量是m3, 因此现在就是z + m3. 我们要判断的就是x + z + m1 + m3是否大于k. 我们知道此时的y + m2 > x + m1. 于是我们有:
S1 + m1 + m2 + m3 – (y + m2) > S1 + m1 + m2 + m3 – (x + m1)的
不等式右边又有:
S1 + m1 + m2 + m3 – (x + m1) == S1 -x + m2 + m3
我们知道S1 – x大于k并且m2 + m3是大于等于0的, 因此不等式右边是大于k的. 由于左侧大于右侧, 那么左侧也是大于k的, 而左侧正是此刻除了b以外, 其他char的total count. 至此, 我们证明完毕.

所以sliding window能成的重要原因就是可以通过逻辑排除.

到这里, right不满足题意, 以left作为start, 以right及其它之后的位置作为end的所有substring都不行, 于是我们记录此时的left和right界定的长度 – 1, 因为不包括right. 然后移动left一格. 此时如果pop走的不是max freq, 此时window里的非max freq char就满足题意了, 我们可以继续走, 至于为什么移动一步left就满足, 见我之前写的注解. 简单来说就是来到right前一定满足非max freq小于大于等于k. 来到了right发现大于k了, 说明引入了非max freq char, 我们左侧如果移走一个, 那window就valid了. 如果pop走的是max freq对应的char, 那么我们就要看pop完后的maxFreq是谁, 再看剩下的其他char的count是否满足题意, 如果是那right可以继续走了, 如果不是那继续移动left. 我们是在right走不动的时候计算maxLength.

网友给的答案很巧妙. 当right走不动的时候, 说明right上一步在的地方框起来的window还满足题意, 现在不行了. 于是我们会计算此时的substring length就是right – left因为我们不包含right. 但是网友不这么干, 它此时先让left右移一位, 此时right – left + 1和之前的right – left一个长度. Left向右移动一位后, 我们记录此时的大小并且和maxLength比较. 目前为止, 不管是移动left前right – left还是移动left后的right – left + 1, 得到的值都是一样. 然后这里就面临了一个问题, 刚才pop出去的是max freq对应的char吗? 如果不是, 那么此时的window已经valid了, right可以继续走; 如果是, 那么此时的window可能是valid, 也可能不是, 常规操作就是去缩left, 然后等到window valid之后再去移动right. 但其实不用缩. 因为我们是求最长的, 那么此时我们的window扩展到了这个地步, 我们就按照这个window size走, 如果后面还能扩, 我们继续更新maxLength, 如果不行我们就维持这个size一直到结束. 不缩window size是这道题的关键.

下面这样写就清晰了:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
    public int characterReplacement(String s, int k) {
        int left = 0, right = 0, maxCount = 0, maxLength = 0;
        int[] count = new int[26];
        while (right < s.length()) {
            // Include a new char
            count[s.charAt(right) - 'A'] += 1;
            maxCount = Math.max(maxCount, count[s.charAt(right) - 'A']);
            
            // If current window is not valid. Move window to right by 1 step
            if (right - left + 1 - maxCount > k) {
                count[s.charAt(left) - 'A'] -= 1;
                maxCount = Math.max(maxCount, count[s.charAt(right) - 'A']);
                left += 1;
            } else {
              // If current window is valid, record current length and update maxLength if necesssary
                maxLength = Math.max(maxLength, right - left + 1);
            }
            right += 1;
        }
        return maxLength;
    }
}

最新感想
这个maxCount不一定是当前window最大的char count而是在这个winodw size下目前为止最大的. 也就是之前可能某个window也是当前的size, 然后maxCount达到了这个值. 为什么要这么做? 首先我们可能会想到sliding window, 于是开始尝试, 当到某个位置后, 发现最大frequency以外的char的count超过了k. 此时满足条件的length就是right - left(因为不包含right). 那么我们就知道, 如果在当前的window size下(right - left + 1), 只要最大freq char的count不超过maxCount, 我们得到的能满足题意的length, 就是right - left这么长. 由于我们要求最长长度, 那么window的size就要突破现在的大小, 并且让maxCount也需要相应的突破.

之前我们证明过, right及其以后的位置作为end的window都不满足题意, 因此我们才移动left, left只移动一格, right也移动一格, 更新被pop出去以及添加进来的char的count, 然后看maxCount是否改变, 如果依然没改变, 说明没有char的maxCount超过之前的maxCount, 也就是说但前window最大的maxCount还没超过之前的, 那此时一定不满足, 此时的right及其右边的位置决定的window也都不满足, 于是继续移动left. 直到某个时刻, 我们发现maxCount超过了之前的最大值, 此时maxCount被更新为之前的值 + 1. 那么此时的window就是valid, 我们就会计算此时的length并且更新maxLength.

说了这么多, 我们是从一开始扩window, 到某个位置扩不动了, 我们知道此时window size - 1的window中, 最长的length是多少. 此时的maxCount是多少. 如果想突破它, 那就必须让maxCount有所增加, 这样length才可能变大. 于是我们保留此时的window, 不缩. 一直右移, 更新着window内char的count. 直到某个时刻有一个char的count大于之前记录的maxCount. 那么此时的window就变为valid了, 那么maxLength也就可以被更新.

关键点在于我们知道某个window size下, 频率最大的char的maxCount是多少. 然后我们维持这个window一直往后, 只要window中频率最大的char的count小于这个数字当前这个window就是不行的, 换句话说, 当前window为start产生的window中能满足题意的size比我们之前得到的结果要小, 于是我们就不予考虑. 只有当某个时刻频率最大的char的count大于之前的maxCount, 此时该window变为valid, maxLength需要被更新, left不需移动, 而是继续移动right, 看是否能进一步扩大window.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
    public int characterReplacement(String s, int k) {
        int left = 0, right = 0;
        int maxCount = 0, maxLength = 0;
        int[] charCount = new int[26];
        while (right < s.length()) {
            charCount[s.charAt(right) - 'A'] += 1;
            maxCount = Math.max(maxCount, charCount[s.charAt(right) - 'A']);
            if (right - left + 1 - maxCount > k) {
                charCount[s.charAt(left) - 'A'] -= 1;
                left += 1;
            } else {
                // We know at current window size, the maxLength is right - left + 1
                // Only we have larger window size and the window is valid, will we enter this else condition.
                maxLength = right - left + 1;
            }
            right += 1;
        }
        return maxLength;
    }
}