6425. 找到最长的半重复子字符串 (opens new window)

1.边界判断

分析：字符子串划分为两类，其中一类是不含重复字符；另一类是连续重复子串。

对于连续重复子串而言，如果重复的长度为2，则可以将该重复子串前后两个非重复子串进行合并。否则此时最长子串为前半段长度加2，或者是后半段长度加2。

本题边界条件非常多：

• 对于两个可合并的非重复子串，是否可以再往各自左右边界再读取连续重复子串的一个字符。(asum用于控制a是否是开头第一个非重复子串，如果不是则a可以向左边扩张)
• 以重复子串段结束或者开头
• 开头第一段非重复子串是否需要预读取(astart控制先读取开头第一个非重复子串)

😭😭😭算法太垃圾，写的想死。

class Solution {
    public static int longestSemiRepetitiveSubstring(String s) {
        int res=0,index=0,a=0,b=0;
        boolean astart=true,asum=true;
        while(index<s.length()){
            boolean merge=false;
            if(astart){
                while(index+1<s.length()&&s.charAt(index)!=s.charAt(index+1)) index++;
                if(index==s.length()-1) return s.length();
                a=index;
                res=Math.max(res,a+2);
                astart=false;
            }
            else{
                int sum=1;
                //计算重复段长度，并将index置为非重复段第一个字符
                while(index+1<s.length()&&s.charAt(index)==s.charAt(index+1)) {
                    index++;
                    sum++;
                }
                index++;
                //搜索以重复段结尾
                if(index==s.length()){
                    if(asum) asum=false;
                    else {
                        a++;
                    }
                    res=Math.max(res,a+2);
                    break;
                }
                //判断是否融合
                merge = sum > 2 ? false : true;
                //下一个非重复段只有一个字符
                if(index==s.length()-1){
                    if(asum) asum=false;
                    else {
                        a++;
                    }
                    b++;
                    if(merge) res=Math.max(res,a+2+b);
                    else res=Math.max(res,b+2);
                    break;
                }
                //计算非重复段长度
                while(index+1<s.length()&&s.charAt(index)!=s.charAt(index+1)){
                    index++;
                    b++; //初始化为0
                }
                //搜索以非重复段结尾
                if(index==s.length()-1) {
                    if(asum) asum=false;
                    else {
                        a++;
                    }
                    b++;
                    if(merge) res=Math.max(res,a+2+b);
                    else res=Math.max(res,b+2);
                    break;
                }
                //后面还有
                else{
                    if(asum) asum=false;
                    else {
                        a++;
                    }
                    if(merge) res=Math.max(res,a+2+b+1);
                    else res=Math.max(res,b+2);
                }
                a=b;
                b=0;
            }
        }
        return res;
    }
}