# 1888. Minimum Number of Flips to Make the Binary String Alternating      • Time: $O(n)$
• Space: $O(n)$
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 class Solution { public: int minFlips(string s) { const int n = s.length(); // count := the number of '0' in even indices // count := the number of '0' in odd indices // count := the number of '1' in even indices // count := the number of '1' in odd indices vector> count(2, vector(2)); for (int i = 0; i < n; ++i) ++count[s[i] - '0'][i % 2]; // Min(make all '0' in even indices + make all '1' in odd indices, // make all '1' in even indices + make all '0' in odd indices) int ans = min(count + count, count + count); for (int i = 0; i < n; ++i) { --count[s[i] - '0'][i % 2]; ++count[s[i] - '0'][(n + i) % 2]; ans = min({ans, count + count, count + count}); } return ans; } }; 
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 class Solution { public int minFlips(String s) { final int n = s.length(); // count := the number of '0' in even indices // count := the number of '0' in odd indices // count := the number of '1' in even indices // count := the number of '1' in odd indices int[][] count = new int; for (int i = 0; i < n; ++i) ++count[s.charAt(i) - '0'][i % 2]; // Min(make all '0' in even indices + make all '1' in odd indices, // make all '1' in even indices + make all '0' in odd indices) int ans = Math.min(count + count, count + count); for (int i = 0; i < n; ++i) { --count[s.charAt(i) - '0'][i % 2]; ++count[s.charAt(i) - '0'][(n + i) % 2]; ans = Math.min(ans, Math.min(count + count, count + count)); } return ans; } } 
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 class Solution: def minFlips(self, s: str) -> int: n = len(s) # count := # Of '0' in even indices # count := # Of '0' in odd indices # count := # Of '1' in even indices # count := # Of '1' in odd indices count = [ * 2 for _ in range(2)] for i, c in enumerate(s): count[ord(c) - ord('0')][i % 2] += 1 # Min(make all '0' in even indices + make all '1' in odd indices, # make all '1' in even indices + make all '0' in odd indices) ans = min(count + count, count + count) for i, c in enumerate(s): count[ord(c) - ord('0')][i % 2] -= 1 count[ord(c) - ord('0')][(n + i) % 2] += 1 ans = min(ans, count + count, count + count) return ans