刷题-力扣-424

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

题目链接

来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/longest-repeating-character-replacement/
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。

题目描述

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

示例 1:

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

示例 2:

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

题目分析

  1. 根据题目描述最长的替换k次的相同字符长度
  2. 首先要遍历字符串s,记录第一次替换的字符的位置,并记录替换n次后的字符长度len
  3. 下一次寻找字符长度从上一次中第一个替换的字符的位置开始,直到替换k次,并把最长的字符长度写入maxLen
  4. 直到遍历字符串的索引(也可以理解为指针)index大于s.length()
  5. 当循环结束后len和maxLen中较大的,即为所求

代码

class Solution {
public:
    int characterReplacement(string s, int k) {
        int maxLen = 0;         /** 最大长度 */
        int len = 0;
        char chr = s[0];
        int index = 0;          /** 遍历s的指针 */
        int repeat = k;
        int restart = 0;
        while (true) {
            if (index >= s.length()) {
                if (repeat > 0) {
                    len = len + repeat > s.length() ? s.length() : len + repeat;
                }
                return maxLen > len ? maxLen : len;
            }
            if (chr != s[index]) {
                if (repeat == k) restart = index;
                if (repeat <= 0) {
                    maxLen = maxLen > len ? maxLen : len;
                    len = 0;
                    index = restart;
                    chr = s[index];
                    repeat = k;
                } else {
                    repeat--;
                    len++;
                    index++;
                }
            } else {
                index++;
                len++;
            }
        }
    }
};
上一篇:前端入门篇(二十三)列表样式优化


下一篇:day005——CSS字体和背景