leetcode【第十八周】以特定次数替换字符并计算最长重复字符串

作者：花生_TL007 | 2024-05-18 11:33:00

踩

leetcode字符串替换次数

问题描述：

Given a string that consists of only uppercase English letters, you can replace any letter in the string with another letter at most ktimes. Find the length of a longest substring containing all repeating letters you can get after performing the above operations.

Note:
Both the string's length and k will not exceed 104.

Example 1:

Input:
s = "ABAB", k = 2

Output:
4

Explanation:
Replace the two 'A's with two 'B's or vice versa.

Example 2:

Input:
s = "AABABBA", k = 1

Output:
4

Explanation:
Replace the one 'A' in the middle with 'B' and form "AABBBBA".
The substring "BBBB" has the longest repeating letters, which is 4.

问题分析：

一开始想先找到出现次数最多的字母，然后考虑在它们各分段间进行K次拼接来组合最长字符串，再计算拼接出来的字符串的长度，后来想想，这样太麻烦，貌似要从更具有数字联系的角度考虑，不过没什么思路，刷了下网上的博客，好吧，要用滑窗【字符串的处理做的不多，不过貌似滑窗还真是个好思想】。所以每次滑窗后从以下的关系考虑：

滑窗的长度-滑窗内出现最多次的字符的次数<=K

也就是说，如果大于K，就是说当前拼接的字符串断掉了，记录下长度，然后把窗口往下挪，看看是否存在比现在更长的能够通过替换K个字符后出现的重复子字符串。

代码实现：

class Solution {
public:
    int characterReplacement(string s, int k) {
        vector
   
   
    
     counts(26,0);
        int maxLen = 0,start=0,res=0;
        for(int i=0;i
    
    
     
     k)
            {
                --counts[s[start]-'A'];
                ++start;
            }
            res = max(res,i-start+1);
        }
        return res;
    }
};

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/花生_TL007/article/detail/588107