We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Minimum Number of Flips to Make the Binary String Alternating

Number: 2017

Difficulty: Medium

Paid? No

Companies: IBM, Google

Problem Description

Given a binary string s, you can perform two types of operations:

  1. Type-1: Remove the character at the start of s and append it to the end (i.e. a cyclic rotation).
  2. Type-2: Pick any character in s and flip its value ('0' becomes '1' and vice-versa).

Return the minimum number of type-2 (flip) operations needed so that s becomes alternating (i.e., no two adjacent characters are the same). The operations can be performed in any sequence.

Key Insights

  • Any number of rotations (type-1 operations) is allowed, which means we can view s as a cyclic string.
  • To easily account for rotations, double the string (s + s) so that every rotation corresponds to a contiguous segment of length n.
  • Precompute two alternating patterns for strings of length 2n:
    • Pattern1: starting with '0' (i.e., "010101...")
    • Pattern2: starting with '1' (i.e., "101010...")
  • Use a sliding window of size n over the double string and count mismatches with both patterns.
  • The minimum flips needed is the smallest mismatch count found for any window compared against the two patterns.

Space and Time Complexity

Time Complexity: O(n), where n is the length of s, because the sliding window traverses the double string in linear time. Space Complexity: O(n), primarily for storing the double string and the two patterns.

Solution

The solution revolves around converting the cyclic nature of the problem to a linear one by creating a new string composed of s concatenated with itself. Then, we generate two reference alternating patterns for the double length:

  • One starting with '0'
  • One starting with '1'

We slide a window of length n over the double string and calculate the number of differences (flips) required to match the alternating patterns. The overall answer is the minimum number of flips across all windows and both alternating patterns. This method takes advantage of the sliding window technique to efficiently update mismatch counts by adding the new element and removing the old one as the window slides.

Code Solutions

# Python solution with line-by-line comments
def minFlips(s: str) -> int:
    n = len(s)
    # Create the double string to cover all cyclic rotations
    s_double = s + s
    
    # Build the two expected alternating patterns of length 2 * n
    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))
    
    # Initial mismatch counts for the first window of length n
    mismatch1 = mismatch2 = 0
    for i in range(n):
        if s_double[i] != pattern1[i]:
            mismatch1 += 1
        if s_double[i] != pattern2[i]:
            mismatch2 += 1

    # Result holds the minimal mismatches (i.e., flips) found so far
    res = min(mismatch1, mismatch2)
    
    # Use sliding window to update mismatch counts for each rotation
    for i in range(n, 2 * n):
        # Index of the element leaving the window
        j = i - n
        
        # If the leaving element was mismatched with pattern1, decrease the count
        if s_double[j] != pattern1[j]:
            mismatch1 -= 1
        # If the new element entering the window does not match pattern1, increment the count
        if s_double[i] != pattern1[i]:
            mismatch1 += 1

        # Do the same for pattern2
        if s_double[j] != pattern2[j]:
            mismatch2 -= 1
        if s_double[i] != pattern2[i]:
            mismatch2 += 1

        # Update result with the minimum flips required so far
        res = min(res, mismatch1, mismatch2)
        
    return res

# Example usage:
print(minFlips("111000"))  # Expected output: 2
← Back to All Questions