2730、找到最长的半重复子字符穿

题目：

解答：

窗口为[left，right]，ans为窗口长度，same为子串长度，窗口满足题设条件，即只含一个连续重复字符，则更新ans，否则从左边开始一直弹出，直到满足条件。

same记录窗口内出现的重复字符串个数。same<2时满足条件。

class Solution {
public:
    int longestSemiRepetitiveSubstring(string s) {
        int len = s.size();
        if(len == 1) return 1;
        int left = 0 ,right = 1;
        int ans= 0;
        int same = 0;
        for(right;right<len;right++){
            if(s[right]==s[right-1])
                same++;
            if(same==2){
                left++;
                while(s[left-1]!=s[left]){
                    left++;
                }
                same--;
            }
            ans=max(ans,right-left+1);
        }
        return ans;
    }
};

时间复杂度O(n)

空间复杂度O(1)

原文地址：https://blog.csdn.net/qq_56272102/article/details/149123924

免责声明：本站文章内容转载自网络资源，如侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！