problem:2730. 找到最长的半重复子字符串

思路：滑动窗口维护窗口里面的相邻字符是相等的子串的个数

Accode:

class Solution {
public:
    int longestSemiRepetitiveSubstring(string s) {
        vector<int> cnt(9,0);
        int len  = s.length();
        int idx_repeat=0,cnt_repeat=0;
        int ans = 0;
        deque<int> deq;
        for(int i=0;i<len;i++){
            while(deq.size() &&s[deq.back()]==s[i]){
                if(cnt_repeat>=1){
                    if(deq.front()<=idx_repeat){
                        deq.pop_front();
                    }
                    else{
                        cnt_repeat--;
                    }
                }
                else break;
            }
            if(deq.size() && s[deq.back()]==s[i]){
                idx_repeat = deq.back();
                cnt_repeat++;
            }
            deq.push_back(i);
            ans = max(ans,(int)deq.size());
        }
        return ans;
    }
};

时间复杂度：$o(n)$