LeetCode 1888 - Minimum Number of Flips to Make the Binary String Alternating

The problem asks us to transform a binary string s into an alternating string using the minimum number of flip operations (Type-2), while optionally performing any number of rotations (Type-1).

leetcodemediumstringdynamic-programmingsliding-window

LeetCode Problem 1888

Difficulty: 🟡 Medium
Topics: String, Dynamic Programming, Sliding Window

Solution

Problem Understanding

The problem asks us to transform a binary string s into an alternating string using the minimum number of flip operations (Type-2), while optionally performing any number of rotations (Type-1). An alternating string is one where no two consecutive characters are the same, so valid alternating strings follow the patterns "010101..." or "101010...".

The first operation allows a rotation: removing the first character and appending it at the end. This means we must consider all cyclic permutations of the string, as any rotation could potentially minimize the number of flips needed. The second operation is a flip: changing a '0' to '1' or '1' to '0'. Our goal is to find the minimum number of flips required across all rotations.

The constraints allow s to be up to 10^5 characters, so brute-force rotation simulation is too slow. We need an efficient way to compute the minimum flips without physically rotating the string each time.

Important edge cases include strings that are already alternating, strings where all characters are the same, and strings of odd versus even lengths, since odd-length strings allow some rotations to change the starting pattern.

Approaches

The brute-force approach would generate all rotations of the string and count the flips required for each rotation to match both "0101..." and "1010..." patterns. While correct, this requires generating n rotations and checking 2*n flips per rotation, giving O(n^2) time complexity. This is infeasible for n = 10^5.

The optimal approach uses a sliding window strategy. We can double the string (s + s) to simulate all rotations, then slide a window of length n across the doubled string. For each window, we count the flips needed to convert it to the "0101..." and "1010..." patterns. Sliding the window allows us to efficiently update the flip count in O(1) time per step using previous counts, resulting in O(n) total time complexity.

Approach Time Complexity Space Complexity Notes
Brute Force O(n^2) O(n^2) Generate all rotations and count flips individually
Optimal O(n) O(n) Use sliding window on doubled string to account for rotations efficiently

Algorithm Walkthrough

  1. Create two reference patterns for the alternating string of length 2n (to handle rotations). Pattern1 starts with '0' and alternates, pattern2 starts with '1' and alternates.
  2. Double the input string to simulate all rotations.
  3. Initialize a window of length n at the start of the doubled string and count the flips required for both patterns in this window.
  4. Slide the window by one character at a time from left to right. For each shift:
  • Update the flip counts by removing the contribution of the character leaving the window and adding the contribution of the character entering the window.
  • Keep track of the minimum flips seen so far across all windows.
  1. Return the minimum flip count after examining all windows of length n.

Why it works: Doubling the string ensures every rotation is represented as a contiguous substring of length n. Comparing against two reference patterns guarantees we account for both valid alternating patterns. The sliding window efficiently computes flips for each rotation without recomputation, giving the correct minimum flips.

Python Solution

class Solution:
    def minFlips(self, s: str) -> int:
        n = len(s)
        s_double = s + s
        pattern1 = ''.join(['0' if i % 2 == 0 else '1' for i in range(2 * n)])
        pattern2 = ''.join(['1' if i % 2 == 0 else '0' for i in range(2 * n)])
        
        flips1 = flips2 = 0
        min_flips = float('inf')
        
        for i in range(2 * n):
            if s_double[i] != pattern1[i]:
                flips1 += 1
            if s_double[i] != pattern2[i]:
                flips2 += 1
            
            if i >= n:
                if s_double[i - n] != pattern1[i - n]:
                    flips1 -= 1
                if s_double[i - n] != pattern2[i - n]:
                    flips2 -= 1
            
            if i >= n - 1:
                min_flips = min(min_flips, flips1, flips2)
        
        return min_flips

The implementation first constructs two alternating patterns of length 2n to account for all rotations. By doubling the string s, we avoid physically rotating it. The sliding window efficiently computes flip counts by updating only the entering and leaving characters, ensuring O(n) time. Finally, the minimum flip count across all windows is returned.

Go Solution

func minFlips(s string) int {
    n := len(s)
    sDouble := s + s
    pattern1 := make([]byte, 2*n)
    pattern2 := make([]byte, 2*n)
    
    for i := 0; i < 2*n; i++ {
        if i%2 == 0 {
            pattern1[i] = '0'
            pattern2[i] = '1'
        } else {
            pattern1[i] = '1'
            pattern2[i] = '0'
        }
    }
    
    flips1, flips2 := 0, 0
    minFlips := n + 1
    
    for i := 0; i < 2*n; i++ {
        if sDouble[i] != pattern1[i] {
            flips1++
        }
        if sDouble[i] != pattern2[i] {
            flips2++
        }
        if i >= n {
            if sDouble[i-n] != pattern1[i-n] {
                flips1--
            }
            if sDouble[i-n] != pattern2[i-n] {
                flips2--
            }
        }
        if i >= n-1 {
            if flips1 < minFlips {
                minFlips = flips1
            }
            if flips2 < minFlips {
                minFlips = flips2
            }
        }
    }
    
    return minFlips
}

The Go implementation mirrors the Python logic, using slices of bytes for pattern representation and maintaining flip counts with a sliding window. There are no special concerns with empty strings since the constraints guarantee 1 <= n. Integer overflow is not a concern because flip counts are bounded by n.

Worked Examples

Example 1: s = "111000"

i Window Flips to "010101" Flips to "101010" Min so far
0-5 "111000" 4 2 2
1-6 "110001" 3 3 2

Output: 2 flips.

Example 2: s = "010"

Already alternating. Minimum flips = 0.

Example 3: s = "1110"

i Window Flips to "0101" Flips to "1010" Min so far
0-3 "1110" 2 1 1

Output: 1 flip.

Complexity Analysis

Measure Complexity Explanation
Time O(n) We iterate over the doubled string once and update flips in O(1) per step using sliding window.
Space O(n) Storing doubled string and two pattern arrays requires linear space.

The sliding window approach avoids recalculating flips for every rotation, reducing a potential O(n^2) algorithm to linear time.

Test Cases

# test cases
sol = Solution()

assert sol.minFlips("111000") == 2  # example 1
assert sol.minFlips("010") == 0     # example 2
assert sol.minFlips("1110") == 1    # example 3
assert sol.minFlips("0") == 0       # single character
assert sol.minFlips("1") == 0       # single character
assert sol.minFlips("111111") == 3  # all same characters
assert sol.minFlips("101010") == 0  # already alternating, even length
assert sol.minFlips("0101") == 0    # already alternating, even length
assert sol.minFlips("1101") == 1    # odd length
Test Why
"111000" general case with rotation needed
"010" already alternating, minimal flips = 0
"1110" requires flips but minimal rotation needed
"0", "1" single-character edge cases
"111111" all identical characters
"101010", "0101" already alternating, even-length
"1101" odd-length string with rotation effect

Edge Cases

Single-character strings: Since a string of length 1 is trivially alternating, no flips are required. Implementation handles this automatically.

All identical characters: Requires approximately half of characters to flip. Sliding window correctly counts