替换后的最长重复字符

Leetcode Link: 424. 替换后的最长重复字符 - 力扣（LeetCode） (leetcode-cn.com)

题目

给你一个字符串 s 和一个整数 k 。你可以选择字符串中的任一字符，并将其更改为任何其他大写英文字符。该操作最多可执行 k 次。

在执行上述操作后，返回包含相同字母的最长子字符串的长度。

解题关键

确定窗口的长度，或者说窗口收缩的条件

解法一

思路： 如果能满足题目的要求，则窗口内最多可以有 max_cnt 个重复的元素（至于重复什么我们不关心）和 k 个跟重复元素不同的元素（这样才能换掉 k 个，最终得到一个满足要求的结果为 max_cnt + k，或者说是此时的 right-left）

那么在每一次出窗和入窗，我们需要做下面的工作：

1. 窗内信息的维护，出窗-1 入窗+1
2. 当前窗口内最大的重复次数（其实我们不关心是那个字符重复次数最多）
3. 判断是不是应该收缩窗口

题解：

class Solution:
    def characterReplacement(self, s: str, k: int) -> int:
        # 每次都进窗，但是不一定每次都出去。
        windows = [0]*26
        # [left, right)
        left = 0
        right = 0
        res = 0
        while(right < len(s)):
            idx_r = ord(s[right])-ord('A')
            windows[idx_r] += 1
            max_cnt = max(windows) # 重复次数最多的重复了多少次
            sum_cnt = sum(windows) # 当前窗内含有的字符个数，也 = right - left
            while(sum_cnt > max_cnt+k ):
                idx_l = ord(s[left])-ord('A')
                windows[idx_l] -= 1
                max_cnt = max(windows)
                sum_cnt = sum(windows)
                left += 1
            right += 1
 
            res = max(res, sum_cnt)
        
        return res
 

我们这里采用了一个数组来表示窗口信息，每次窗口变化通过 max() 可以快速求出重复的次数，但是有点慢，因为每次都要 max 一下。但是如果是只和当前比：max_cnt=max(max_cnt, window[self.getInd(rc)])，似乎max_cnt不能变小了，就不能准确反应当前窗内的最大重复次数 开始用字典，卡在了出窗那里，要是出去了一个max_cnt的，不知道咋判断第二大的重复次数和max_cnt的关系，因为找不到第二大的重复次数，要搞一个迭代，感觉有点麻烦。

解法二

思路： 对于思路 1 的优化，主要是删除了 res，并且改变了 max () 函数的位置和内容

原因：max_cnt 其实可以不和当前窗内的最大次数有关，它只和到目前位置的最大重复次数有关，在找到结果的时候窗口大小就会固定了下来，并会一直保持到算法结束，因此返回的是right-left.

题解：

class Solution:
    def characterReplacement(self, s: str, k: int) -> int:
        # 窗口长度为max_cnt+k
        max_cnt = left = right = 0
        window = [0]*26
        while(right < len(s)):
            ### 入窗
            rc = s[right]
            right += 1
            window[self.getInd(rc)] += 1
            # 找出现最多的元素个数
            max_cnt = max(max_cnt, window[self.getInd(rc)])
            ### 出窗判断，窗口的宽度为max_cnt+k，即最多可以替换k次
            while(right-left > max_cnt+k):
                lc = s[left]
                left += 1
                window[self.getInd(lc)] -= 1
 
        return right-left
	# 字符变成索引
    def getInd(self, c: str):
        return ord(c)-ord('A')

启发和联系

# 字符变成索引
def getInd(self, c: str):
    return ord(c)-ord('A')

滑动窗口类问题，有这样可能的一个策略

1. 每次都入窗，但是不一定每次都出窗。要十分明确出窗的条件。