[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;
    }
};