【每日一题】 424. 替换后的最长重复字符

怼烎@ 2022-10-29 06:29 54阅读 0赞

# 【每日一题】 424. 替换后的最长重复字符 #

> 避免每日太过咸鱼，一天搞定一道LeetCode算法题

## 一、题目描述 ##

难度： **中等**

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

**提示：**

*  字符串长度 和 *k* 不会超过 104。

**示例 1：**

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

**示例 2：**

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

## 二、题解 ##

### 1. 解法 ###

### **解题思路：** ###

*  本题是比较典型的滑动窗口问题
 *  这类问题一般通过一个滑动窗口就能在 O(N)*O*(*N*) 的时间复杂度下求解

本题可以先退化成考虑 K=0*K*=0 的情况，此时题目就变成了求解字符串中最长连续子串长度问题了。  
我们先可以通过这个特例先了解一下滑动窗口的求解过程

\[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-DLmwDrkC-1612839793418)(./img/19-1.jpg)\]

上图的求解过程展示中，窗口从左至右不断扩张/滑动，当窗口触达字符串末尾字符时，运算结束，窗口的宽度为最终结果。初始窗口的宽度为 1，我们不断的通过向当前窗口覆盖的子串后面追加一个字符看是否能满足我们的要求，如果满足窗口扩张，如果不满足，窗口向右滑动。

当 K>0时，子串的条件变成了允许我们变换子串中的 K 个字符使其变成一个连续子串

那么这个题的关键点就是我们如何判断一个字符串改变 K个字符，能够变成一个连续串

如果当前字符串中的出现次数最多的字母个数 +K大于串长度，那么这个串就是满足条件的

我们维护一个数组 int\[26\] 来存储当前窗口中各个字母的出现次数，left表示窗口的左边界，right 表示窗口右边界

*  窗口扩张：left不变，right++
 *  窗口滑动：left++，right++

historyCharMax 保存滑动窗口内相同字母出现次数的 历史 最大值，通过判断窗口宽度 (right - left + 1)是否大于 historyCharMax + K 来决定窗口是否做滑动，否则窗口就扩张。

**代码**

public int characterReplacement(String s, int k) { 
        int[] map = new int[26];
        int left = 0, right = 0, historyCharMax = 0;
        char[] chars = s.toCharArray();
        for (right = 0; right < chars.length; right++) { 
            int index = chars[right] - 'A';
            map[index]++;
            historyCharMax = Math.max(historyCharMax, map[index]);
            if (right - left + 1 > historyCharMax + k) { 
                map[chars[left] - 'A']--;
                left++;
            }
        }
        return right - left ;
    }

**复杂度分析**

*  时间复杂度：O(n)，其中 *n* 是字符串的长度。我们至多只需要遍历该字符串一次。
 *  空间复杂度：*O*(∣Σ∣)，其中 ∣Σ∣ 是字符集的大小。我们需要存储每个大写英文字母的出现次数。

题目来源：力扣（LeetCode）  
链接：https://leetcode-cn.com/problems/distance-between-bus-stops

\--------------最后感谢大家的阅读，愿大家技术越来越流弊！--------------

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1phY2tfdHpo_size_16_color_FFFFFF_t_70]

\--------------也希望大家给我点支持，谢谢各位大佬了！！！--------------

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1phY2tfdHpo_size_16_color_FFFFFF_t_70]: /images/20221024/3ffe830bc1614ed1bface0bb142e5887.png