LeetCode 1156 单字符重复子串的最大长度
🟡 中等 https://leetcode.cn/problems/swap-for-longest-repeated-character-substring/description/
暴力滑动搜索
O(n*n)
对于每个开始，可以先滑动一段距离，找到第一个不同的元素，再尝试滑动第二段举例即可。
class Solution {
public:
int maxRepOpt1(string text) {
int count[26];
fill(count,count+26,0);
for(int i = 0;i<text.size();i++){
count[text[i]-'a']++;
}
int res = 0;
for(int i = 0;i<text.size();i++){
int first = i;
while(first<text.size()&&text[first]==text[i]) first++;
int second = first+1;
while(second<text.size()&&text[second]==text[i]) second++;
res = max(res,min(second-1-i+1,count[text[i]-'a']));
}
return res;
}
};
巧妙滑窗
使用和[17-395至少有K个重复字符的最长子串](LeetCode 395 至少有 K 个重复字符的最长子串 - 滑动窗口解法.md) 主动限制窗口内的元素；注意到主要的元素只有26种可能，因此，可以每层循环指定主要的元素是哪个。
第一次：滑窗限制条件为至多有1个元素不等于 a。 第二次：至多有一个元素不等于b。
复杂度为：O(n*m) 。
class Solution {
public:
int maxRepOpt1(string text) {
int count[26];
fill(count,count+26,0);
for(char& ch:text) count[ch-'a']++;
int res = 0;
for(char ch = 'a';ch<='z';ch++){
int left = 0;
int not_equal = 0;
for(int i = 0;i<text.size();i++){
not_equal+=(text[i]!=ch);
while(not_equal>1){
not_equal-=(text[left]!=ch);
left++;
}
res = max(res,min(i-left+1,count[ch-'a']));
}
}
return res;
}
};