leetcode 424.替换后的最长重复字符

题干

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

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

示例 1：

输入：s = “ABAB”, k = 2

输出：4

解释：用两个’A’替换为两个’B’,反之亦然。

示例 2：

输入：s = “AABABBA”, k = 1

输出：4

解释：

将中间的一个’A’替换为’B’,字符串变为 “AABBBBA”。

子串 “BBBB” 有最长重复字母, 答案为 4。

题解

滑动窗口，不断向右移动边界，当区间不满足是右移左边界，如此区间长度一定恒为最大区间（扩展右界后不满足会右移左界以维持区间长度稳定）

class Solution {
   public:    int characterReplacement(string s, int k) {
           int n = s.length();        if(n == 0 || n == 1){
               return n;        }        vector
   
     count(26,0);        int leftBound = 0,rightBound = 0;        int maxContinuousSameLetterCount = 0;        while(rightBound < n){
               count[s[rightBound] - 'A']++;            maxContinuousSameLetterCount = max(maxContinuousSameLetterCount,count[s[rightBound] - 'A']);            //区间内无论如何变换也不能统一字母的情况            if(rightBound - leftBound + 1 - maxContinuousSameLetterCount > k){
                   count[s[leftBound] - 'A']--;                leftBound++;            }            rightBound++;        }        //跳出循环时rightBound会+1，所以返回答案时不用再+1        return rightBound - leftBound;    }};//即寻找一个最长的子串，该子串中较少的字符最多有k个

转载地址：http://gcqmz.baihongyu.com/

你可能感兴趣的文章