1156. 单字符重复子串的最大长度

只要无惧于尝试，没有人会彻底失败。

LC每日一题，参考1156. 单字符重复子串的最大长度。

题目

如果字符串中的所有字符都相同，那么这个字符串是单字符重复的字符串。

给你一个字符串 text，你只能交换其中两个字符一次或者什么都不做，然后得到一些单字符重复的子串。返回其中最长的子串的长度。

输入：text = "ababa"
输出：3
输入：text = "aaabaaa"
输出：6
输入：text = "aaabbaaa"
输出：4
输入：text = "aaaaa"
输出：5
输入：text = "abcdef"
输出：1

解题思路

• 滑动窗口：遍历字符串,每次碰到不同的字符时,计算交换一次的最长子串,之后开始新的字符统计。

滑动窗口

class Solution {
    public int maxRepOpt1(String text) {
        //考虑滑动窗口
        char[] tc = text.toCharArray();
        int n = tc.length;
        //首先统计字符计数
        int[] count = new int[26];
        for(int i = 0; i < n; i++) count[tc[i]-'a'] ++;
        //遍历连续字符 如果碰到不同的字符可以根据剩余该字符来判断是否能交换
        int ans = 1,i = 1,max = 1;
        char pre = tc[0];
        while(i < n) {//统计每个字符开始后的最长
            if(tc[i] == pre) {
                i++;
                max++;
                ans = Math.max(ans,max);
            }else{ //尝试交换
                if(count[pre-'a'] > max) {
                    int j = i+1,add = 0;
                    while(j < n && tc[j] == pre){
                        add++;//交换后最多增加的长度
                        j++;
                    } 
                    if(max + add < count[pre-'a']) max += add + 1;
                    else max += add;
                    ans = Math.max(ans,max);
                }
                //开始新字符统计
                pre = tc[i++];
                max = 1;
            }
        }
        if(count[pre-'a'] > max) ans = Math.max(ans,max+1);//最后一个字符
        return ans;
    }
}

复杂度分析

• 时间复杂度：O(n)，访问字符串次数不超过2n,n为字符串长度。
• 空间复杂度：O(k)，哈希计数空间固定为k = 26。