1156. 单字符重复子串的最大长度 (opens new window)

1.滑动窗口

使用哈希保存每个字符的总共出现的次数。问题的抽象过程为：

交换字符获得重复子串的最大长度⏩交换字符后能够使区间长度扩大⏩找到相隔一个字符的两个区间进行合并。

问题转化的核心在于，有了哈希表的词频统计，设计算法时并不需要关注“交换”这一个操作。只要当前连续区间或者是两个间隔一个字符的连续区间的长度，小于哈希表中该字符的使用频次，那么就说明对于当前连续区间，肯定可以通过交换在其它位置上的该字符来实现扩张。而这个字符究竟是在遍历顺序的前还是后？又是否是出现在当前连续区间内？以及交换两个字符后扩张的区间是通过前一个还是后一个字符连起来的？这些“交换”问题完全都不需要考虑。

因此对于一个连续区间，需要搜索的步骤包含以下几步：

• 当前连续区间的长度是否等于字符的总出现次数，是则说明当前字符区间不可再扩张
• 找到当前连续区间隔了一个字符后下一个连续区间，如果该区间是可合并的，那么更新最大区间长度。
• 通过头尾指针维护滑动窗口，扩张完当前区间后，更新头尾指针到下一个区间。

class Solution {
    public int maxRepOpt1(String text) {
        HashMap<Character,Integer> map=new HashMap<>();
        for(int i=0;i<text.length();i++){
            map.put(text.charAt(i),map.getOrDefault(text.charAt(i),0)+1);
        }
        int ans=1;
        for(int i=0;i<text.length();){
            int j=i;
            while(j<text.length()&&text.charAt(j)==text.charAt(i)) j++;
            if(j-i==map.get(text.charAt(i))){
                ans=Math.max(ans,map.get(text.charAt(i)));
                i=j;
                continue;
            }
            else{
                ans = Math.max(ans, j - i + 1);
                if (j >= text.length() - 1) break;
                int nexti = j + 1, nextj = j + 1;
                if (text.charAt(nexti) != text.charAt(i)) {
                    i=j;
                    continue;
                }
                //找到下一个连续区间
                while (nextj < text.length() && text.charAt(i) == text.charAt(nextj)) nextj++;
                int len=j - i + nextj - nexti==map.get(text.charAt(i))?j - i + nextj - nexti:j - i + nextj - nexti+1;
                ans = Math.max(ans, len);
                i = j;
            }
        }
        return ans;
    }
}