【python-leetcode424-滑动窗口法】替换后的最长重复字符

发布时间：2020-12-20 09:55:08 所属栏目：Python 来源：网络整理

导读：问题描述：给你一个仅由大写英文字母组成的字符串，你可以将任意位置上的字符替换成另外的字符，总共可最多替换?k?次。在执行上述操作后，找到包含重复字母的最长子串的长度。注意: 字符串长度和 k 不会超过?104。示例 1: 输入: s = "ABAB",k = 2 输出:

问题描述：

给你一个仅由大写英文字母组成的字符串，你可以将任意位置上的字符替换成另外的字符，总共可最多替换?k?次。在执行上述操作后，找到包含重复字母的最长子串的长度。

注意:
字符串长度和 k 不会超过?104。

示例 1:

输入:
s = "ABAB",k = 2

输出:
4

解释:
用两个'A'替换为两个'B',反之亦然。
示例 2:

输入:
s = "AABABBA",k = 1

输出:
4

解释:
将中间的一个'A'替换为'B',字符串变为 "AABBBBA"。
子串 "BBBB" 有最长重复字母,答案为 4。

暴力法的滑动窗口就不写了，直接看升级版的。

具体思路看源码中的注释。

class Solution:
    def characterReplacement(self,s: str,k: int) -> int:
        from collections import defaultdict
        hash = defaultdict(int) #用于存储字符出现的次数
        start = 0 左窗口
        maxCount = 0 用于存储当前出现次数最多的字符的次数
        res = 0 存储结果
        for i in range(len(s)): i表示右窗口
            遍历到一个字符，在hash中的次数就加一
            hash[s[i]] += 1
             当前窗口中元素最多的字符的次数
            maxCount = max(maxCount,hash[s[i]])
             当前窗口里的字符的个数减去当前窗口里字符出现的最大值如果大于k，
             说明修改k次不能满足条件了，则在左端窗口处的字符值-1，同时往前进一位
            while i - start + 1 - maxCount > k: 这里其实可以用if
                hash[s[start]] -= 1
                maxCount = max(maxCount,hash[s[start]]) 更新一下maxCount，这里其实也可省略掉。
                start += 1
                
            res = max(i - start + 1,res)
        return res

结果：

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!