1156 Swap For Longest Repeated Character Substring 单字符重复子串的最大长度
描述
如果字符串中的所有字符都相同，那么这个字符串是单字符重复的字符串。
给你一个字符串text，你只能交换其中两个字符一次或者什么都不做，然后得到一些单字符重复的子串。返回其中最长的子串的长度。
- 示例 1：
输入：text = "ababa"
输出：3
解释: 我们可以用最后一个“a”替换第一个“b”，或者用第一个“a”替换最后一个“b”。然后，最长的重复字符子串是“aaa”，其长度为3
- 示例 2：
输入：text = "aaabaaa"
输出：6
解释: 用最后一个“a”(或第一个“a”)替换“b”，我们得到最长的重复字符子串“aaa”，其长度为6
- 示例 3：
输入：text = "aaabbaaa"
输出：4
- 示例 4：
输入：text = "aaaaa"
输出：5
解释: 无需交换，最长重复字符子串为“aaa”，长度为5
- 示例 5：
输入：text = "abcdef"
输出：1
- 提示：
1 <= text.length <= 20000
text 仅由小写英文字母组成。
思路
滑动窗口思想
维持一个'窗口', 它拥有左右边界, 并且可以扩展
本题中, '窗口'以某一位置为起点, 向右移动,
1)等于原位置字符的,则+1,
2)不等于的,则看右边还有没有可以交换的相等字符并有没有容错空间(原为1, 使用后为0)
- 注意:特殊情况
"aaba" 这种右边有交换字符, 但紧接着容错字符(不相等但可以容忍的), 会计算出超过字符频数的结果
代码实现
class Solution {
public int maxRepOpt1(String text) {
if (null == text | text.length() <= 0) return 0;
int len = text.length();
char[] chs = text.toCharArray();
//cnt 字符串中所出现字符的频数
int[] cnt = new int[30];
// type 字符串中字符种类
int type = 0;
for (char c : chs) {
int ind=c-'a';
if (cnt[ind]==0) type++;
cnt[ind]++;
}
// 字符串中字符没有重复
if (type == len) return 1;
// 字符串中字符全部单字符重复
if (type == 1) return len;
// size 重复子串最大长度/滑动窗口最大长度
int size = 0;
for (int i = 0; i < len;) {
char begin = chs[i];
// now 当前重复子串最大长度
// time 容错余裕 可以结合字符频数提前判断
// cnt[begin-'a']==1 --> time=0 没有可以交换字符 容错余裕为0
// next 下一个窗口开始位置(因为i++ 会导致有些计算冗余 可以直接从容错位置开始)
int now = 0, time = 1, next=i+1;
// 滑动窗口向右扩展
for (int j = i; j < len; j++) {
// 相等
if (chs[j]==begin) now++;
// 不相等 但有容错和可交换字符
else if ((time-- > 0) && (cnt[begin-'a']-now >= 1)) {now++; next=j;}
else break;
}
// 特殊情况 计算长度必定不大于字符频数
now = now > cnt[begin-'a'] ? cnt[begin-'a'] : now;
// 比较原最大长度与当前长度
size = now > size ? now : size;
i = next;
}
return size;
}
}