花花酱 LeetCode 1888. Minimum Number of Flips to Make the Binary String Alternating

You are given a binary string s. You are allowed to perform two types of operations on the string in any sequence:

• Type-1: Remove the character at the start of the string s and append it to the end of the string.
• Type-2: Pick any character in s and flip its value, i.e., if its value is '0' it becomes '1' and vice-versa.

Return the minimum number of type-2 operations you need to perform such that s becomes alternating.

The string is called alternating if no two adjacent characters are equal.

• For example, the strings "010" and "1010" are alternating, while the string "0100" is not.

Example 1:

Input: s = "111000"
Output: 2
Explanation: Use the first operation two times to make s = "100011".
Then, use the second operation on the third and sixth elements to make s = "101010".

Example 2:

Input: s = "010"
Output: 0
Explanation: The string is already alternating.

Example 3:

Input: s = "1110"
Output: 1
Explanation: Use the second operation on the second element to make s = "1010".

Constraints:

• 1 <= s.length <= 105
• s[i] is either '0' or '1'.

Solution: Sliding Window

Trying all possible rotations will take O(n²) that leads to TLE, we have to do better.

concatenate the s to itself, then using a sliding window length of n to check how many count needed to make the string in the window alternating which will cover all possible rotations. We can update the count in O(1) when moving to the next window.

Time complexity: O(n)
Space complexity: O(1)

 // Author: Huahua class Solution { public: int minFlips(string s) { const int n = s.length(); int ans = INT_MAX; for (int i = 0, c0 = 0, c1 = 1, a0 = 0, a1 = 0; i < 2 * n; ++i, c0 ^= 1, c1 ^= 1) { if (s[i % n] - '0' != c0) ++a0; if (s[i % n] - '0' != c1) ++a1; if (i < n - 1) continue; if (i >= n) { if (s[i - n] - '0' != c0 ^ (n & 1)) --a0; if (s[i - n] - '0' != c1 ^ (n & 1)) --a1; } ans = min({ans, a0, a1}); } return ans; } };