[LeetCode] 2730. Find the Longest Semi-Repetitive Substring

先將 s 轉成 prefix 再套不定長的 Sliding Window 套 pattern

class Solution {
public:
    int longestSemiRepetitiveSubstring(string s) {
        int n = s.size();
        auto trans = [&](string& s) -> vector<int> {
            vector<int> res{0};
            for (int i = 1; i < n; i++) {
                res.push_back(s[i-1] == s[i] ? res.back() + 1 : res.back());
            }
            return res;
        };
        auto nums = trans(s);
        
        int left = 0, right = 0, res = 0;
        while (right < n) {
            int num = nums[right++];
            while (num - nums[left] > 1) left++;
            res = max(res, right-left);
        } 
        return res;
    }
};

不用先轉直接處理

class Solution {
public:
    int longestSemiRepetitiveSubstring(string s) {
        int n = s.size();
        auto check = [&](int i) -> bool {
            if (i == 0) return false;
            return s[i] == s[i-1];
        };
        
        int left = 0, right = 0, res = 0;
        int curr = 0; 
        while (right < n) {
            if (check(right++)) curr++;
            while (curr > 1) {
                if (check(++left)) curr--;
            }
            res = max(res, right-left);
        } 
        return res;
    }
};

左指針快進版

class Solution {
public:
    int longestSemiRepetitiveSubstring(string s) {
        int n = s.size();
        auto check = [&](int i) -> bool {
            if (i == 0) return false;
            return s[i] == s[i-1];
        };
        
        int left = 0, right = 0, res = 0;
        int last = 0;
        while (right < n) {
            bool flag = check(right++);
            if (flag) {
                left = last;
                last = right-1;
            }

            res = max(res, right-left);
        } 
        return res;
    }
};