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

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Minimum Number of Flips to Make the Binary String Alternating

Difficulty: Medium

Problem Description

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

  1. Remove the character at the start of the string s and append it to the end of the string.
  2. Pick any character in s and flip its value.

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.

Key Insights

  • An alternating string should have no two adjacent characters that are the same.
  • We can identify two possible valid alternating patterns: starting with '0' and starting with '1'.
  • The number of flips needed can be calculated by comparing the current string with these two patterns.
  • We can utilize a sliding window approach to efficiently calculate the number of necessary flips after each rotation of the string.

Space and Time Complexity

Time Complexity: O(n), where n is the length of the string.
Space Complexity: O(1), since we are using a constant amount of space regardless of input size.

Solution

To solve the problem, we can compare the string against two target alternating patterns: one starting with '0' (i.e., "010101...") and one starting with '1' (i.e., "101010..."). For each character in the string, we count how many flips are necessary to convert the string into each of these patterns. The minimum number of flips from the two counts will be our answer.

We can also utilize a sliding window approach where we consider the string as circular by effectively concatenating it with itself, allowing us to simulate the rotation. This way, we can efficiently count flips for each possible starting point.

Code Solutions

def minFlips(s: str) -> int:
    n = len(s)
    # Create the two alternating patterns
    target1 = ''.join('01'[(i % 2)] for i in range(n))  # starts with '0'
    target2 = ''.join('10'[(i % 2)] for i in range(n))  # starts with '1'

    # Function to count flips required to convert s to target
    def count_flips(target):
        flips = 0
        for char1, char2 in zip(s, target):
            if char1 != char2:
                flips += 1
        return flips

    # Count flips for both patterns
    flips_for_target1 = count_flips(target1)
    flips_for_target2 = count_flips(target2)

    # Return the minimum flips needed
    return min(flips_for_target1, flips_for_target2)
← Back to All Questions