题目大意：
单字符重复子串的最大长度
如果字符串中的所有字符都相同，那么这个字符串是单字符重复的字符串。
给你一个字符串 text，你只能交换其中两个字符一次或者什么都不做，然后得到一些单字符重复的子串。返回其中最长的子串的长度。
示例 1：
输入：text = "ababa" 输出：3
示例 2：
输入：text = "aaabaaa" 输出：6
示例 3：
输入：text = "aaabbaaa" 输出：4
示例 4：
输入：text = "aaaaa" 输出：5
示例 5：
输入：text = "abcdef" 输出：1
提示：
1 <= text.length <= 20000text仅由小写英文字母组成。
如果想查看本题目是哪家公司的面试题，请参考以下免费链接： https://leetcode.jp/problemdetail.php?id=1156
解题思路分析：
我们需要先对字符串进行一下整理，因为只存在小写字母，所以我们可以找出每个字母所有的单字符重复子串所在的位置。举个例子，比如:
text = "aaabbaaa";
字母a的单字符重复子串有[0, 2], [5, 7]， 字母b则是[3, 4]。统计出每个字母所有连续子串所在位置之后，对于每个字母，我们分别比较两个相邻的子串区间，如果区间之间的间隔为1，那么我们可以肯定一点，这两个区间至少是可以通过一次交换合并在一起的，交换方式是利用中间间隔的那一个字符与两个区间的边缘进行交换，比如”aabaaa”，我们使用b与最左边或者最右边的a进行交换，可以得到”baaaaa”或者”aaaaab”，此时的长度为两个区间的长度和。另外还存在一种可能，如果该字母的子串个数大于2，比如”aabaaaca”，这时，对于前两个子串aa和aaa，将他们合并的最好方式是利用这两个子串之外的a与b进行交换，变成”aaaaaacb”，这时，最长连续区间变为两个区间的长度和加1。
上面讨论的是两个子串区间间隔为1的情况，如果间隔大于1，我们无论如何是无法合并2个区间的，这时最优的方式是从区间长度较小的一方移动一个字母到区间较长的一方的边缘，比如”aabbaaa”，最优的交换方式为”abbaaaa”。
实现代码：
public int maxRepOpt1(String text) {
List<int[]>[] memo = new List[26]; // 用于记录每个字母的连续区间
for(int i=0;i<26;i++) memo[i]=new ArrayList<>();
char preC = text.charAt(0);
int startIndex=0;
// 统计每个字母的连续区间
for(int i=1;i<text.length();i++){
char c = text.charAt(i);
if(c!=preC){
memo[preC-'a'].add(new int[]{startIndex, i-1});
startIndex=i;
preC=c;
}
if(i==text.length()-1) memo[c-'a'].add(new int[]{startIndex, i});
}
int res=1; // 返回结果
// 循环每个字母
for(List<int[]> list : memo){
int[] pre=new int[]{-3,-3};
// 循环当前字母的所有连续区间
for(int i = 0;i<list.size();i++){
// 当前区间
int[] current=list.get(i);
// 当前区间与前区间间隔为1（例0和2间隔1，2-0=2）
if(current[0]-pre[1]==2){
// 两个区间可以合并，合并后长度为current[1]-pre[0]
// 如果还有其他区间，可以使用其他区间的当前字母填充中间的间隔，长度再加一
res=Math.max(res,current[1]-pre[0]+(list.size()>2?1:0));
}else{
// 当前区间与前区间间隔大于1
// 无法合并，当前区间长度为current[1]-current[0]+1
// 如果还存在其他区间，可以使用其他区间的一个字母添加到当前区间首或尾
res=Math.max(res,current[1]-current[0]+1+(list.size()>1?1:0));
}
pre=current;
}
}
return res;
}本题解法执行时间为6ms。
Runtime: 6 ms, faster than 54.67% of Java online submissions for Swap For Longest Repeated Character Substring.
Memory Usage: 35.7 MB, less than 100.00% of Java online submissions for Swap For Longest Repeated Character Substring.
本网站文章均为原创内容，并可随意转载，但请标明本文链接如有任何疑问可在文章底部留言。为了防止恶意评论，本博客现已开启留言审核功能。但是博主会在后台第一时间看到您的留言，并会在第一时间对您的留言进行回复！欢迎交流！
本文链接: https://leetcode.jp/leetcode-1156-swap-for-longest-repeated-character-substring-解题思路分析/