[LeetCode] 1888. Minimum Number of Flips to Make the Binary String Alternating

難度分: 2006

這一題如果沒有條件一，則很簡單，根據奇偶數索引位置，判斷是否要 flip 就可以了。

int minFlips(string s) {
    int n = s.size();
    int ans1 = 0, ans2 = 0;
    for (int i = 0; i < n; i++) {
        if ((i % 2 == 0 && s[i] != '1') || (i % 2 == 1 && s[i] != '0')) ++ans1;
        if ((i % 2 == 0 && s[i] != '0') || (i % 2 == 1 && s[i] != '1')) ++ans2;
    }
    int ans = min(ans1, ans2);
}

但這一題加上條件一，可以用很精巧的手法，把它轉成 sliding window 的問題，將字串重覆兩次，以原字串長度作為 window size，可解這題。

class Solution {
public:
    int minFlips(string s) {
        int k = s.size();
        s += s;

        int ans1 = 0, ans2 = 0;
        
        for (int i = 0; i < k; i++) {
            if ((i % 2 == 0 && s[i] != '1') || (i % 2 == 1 && s[i] != '0')) ++ans1;
            if ((i % 2 == 0 && s[i] != '0') || (i % 2 == 1 && s[i] != '1')) ++ans2;
        }
        int ans = min(ans1, ans2);

        for (int i = k; i < s.size(); i++) {
            if ((i % 2 == 0 && s[i] != '1') || (i % 2 == 1 && s[i] != '0')) ++ans1;
            if ((i % 2 == 0 && s[i] != '0') || (i % 2 == 1 && s[i] != '1')) ++ans2;
            
            if (((i - k) % 2 == 0 && s[i - k] != '1') || ((i - k) % 2 == 1 && s[i - k] != '0')) --ans1;
            if (((i - k) % 2 == 0 && s[i - k] != '0') || ((i - k) % 2 == 1 && s[i - k] != '1')) --ans2;

            ans = min({ans1, ans2, ans});
        }

        return ans;
    }
};