{x}
blog image

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 Explanation for Minimum Number of Flips to Make the Binary String Alternating

This problem asks to find the minimum number of flips required to make a binary string alternating, considering cyclic rotations of the string. The solution uses a sliding window approach combined with a clever observation to optimize the calculation.

Approach

  1. Alternating Targets: We define two alternating strings as targets: "0101..." and "1010...".

  2. Initial Count: We first calculate the number of flips needed to transform the original string into each target string. This is done by iterating through the string and comparing each character with the corresponding character in the target string. The count of mismatches represents the number of flips needed.

  3. Sliding Window: To account for cyclic rotations, we use a sliding window technique. Instead of explicitly rotating the string, we observe that when we move the window by one position, the mismatch count changes only at two positions: the character leaving the window and the character entering the window. By efficiently updating the count using this observation we avoid redundant calculations.

  4. Minimum Flips: We update the minimum number of flips needed as we slide the window through all possible rotations, keeping track of the minimum value among both targets.

Time and Space Complexity

  • Time Complexity: O(N), where N is the length of the string. We iterate through the string once to calculate the initial counts and then iterate again using a sliding window, performing constant time updates at each step.

  • Space Complexity: O(1). The algorithm uses only a few constant-size variables to store the counts and the minimum number of flips.

Code Explanation (Python)

class Solution:
    def minFlips(self, s: str) -> int:
        n = len(s)
        target = "01"
        cnt = sum(c != target[i & 1] for i, c in enumerate(s)) #Initial count for "01" target
        ans = min(cnt, n - cnt) #minimum flips for "01" target
 
        for i in range(n): #Sliding Window
            cnt -= s[i] != target[i & 1] #Character leaving the window
            cnt += s[i] != target[(i + n) & 1] #Character entering the window
            ans = min(ans, cnt, n - cnt) #Update minimum
 
        return ans

The Java, C++, Go, and TypeScript solutions follow a very similar pattern, adapting the core logic to their respective syntax and libraries. The key idea of the sliding window for efficient calculation remains the same across all implementations.