Leetcode-424-替换后的最长重复字符

题目描述

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

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

示例 1：

输入：s = "ABAB", k = 2
输出：4
解释：用两个'A'替换为两个'B',反之亦然。

示例 2：

输入：s = "AABABBA", k = 1
输出：4
解释：
将中间的一个'A'替换为'B',字符串变为 "AABBBBA"。
子串 "BBBB" 有最长重复字母, 答案为 4。

方法一 ： 滑动窗口

说一下暴力解法：

• 如果一个问题暂时没有思路，可以先考虑暴力解法（不一定要实现）。当前问题的暴力解法是：枚举输入字符串的 所有 子串，对于每一个子串：

  • 如果子串里所有的字符都一样，就考虑长度更长的子串；
  • 如果当前子串里出现了至少两种字符，要想使得替换以后所有的字符都一样，并且重复的、连续的部分更长，应该替换掉出现次数最多字符 以外 的字符。

暴力解法的缺点：

• 做了重复的工作，子串和子串有很多重合的部分，重复扫描它们是不划算的；
• 做了很多没有必要的工作：
  • 如果找到了一个长度为 L 且替换 k 个字符以后全部相等的子串，就没有必要考虑长度小于等于 L 的子串，因为题目只让我们找到符合题意的最长的长度；
  • 如果找到了一个长度为 L 且替换 k 个字符以后不能全部相等的子串，左边界相同、长度更长的子串一定不符合要求（原因我们放在最后说）。

---

滑动窗口

• 以 s = AABCABBB，k = 2 为例，寻找替换 k 次以后字符全部相等的最长子串的长度的过程如下图所示：

---

• 整个过程，我们使用了两个表示边界的变量，一前一后，交替在字符串上前进

• 右边界先向右移动，直到不能移动了为止，左边界再继续向右移动，整个过程像极了一条滑动的窗口在线段上移动。

• 除此之外，考虑的子串中最多出现的字符是次数，因此须要一个频数数组，记录每个字符出现的次数。

class Solution {
    public int characterReplacement(String s, int k) {
        // 1. 特判
        int len = s.length();
        if(len < 2){                                // 长度为0或1
            return len;
        }

        // 2. 初始化条件
        char[] charArray = s.toCharArray();
        int left  = 0;
        int right = 0;

        int res = 0;
        int maxCount = 0;
        int[] freq = new int[26];                   // 记录字符出现的频率

        // 3. 遍历一次字符数组
        while(right < len){
            // 3.1 在这里维护maxCount,因为每一次右边界读入一个字符，字符的频率增加，才会使得maxCount增加
            freq[charArray[right] - 'A']++;
            maxCount = Math.max(maxCount,freq[charArray[right] - 'A']);
            right++;

            // 3.2 
            if(right - left > maxCount + k){        // 说明此时的k不够用，其他不适 最多出现的字符替换以后，都不能填满这个滑动窗口
                freq[charArray[left] - 'A']--;      // 移出滑动窗口的时候，频数数组须要相应地做减法
                left++;                             // 左边界向右移动
            }
            // 3.3 
            res = Math.max(res,right - left);
        }
        return res;
    }
}

复杂度分析：

• 时间复杂度：O(N)，这里 N 是输入字符串 S 的长度；
• 空间复杂度：O(A)，这里 AA 是输入字符串 S 出现的字符 ASCII 值的范围

打赏