Problem Statement in English

You’re given a binary string s. You can perform two types of operations on the string in any sequence:

  1. Type-1: Remove the character at the start of s and append it to the end of s.
  2. Type-2: Flip the character at the start of s (i.e., if it’s ‘0’, change it to ‘1’, and if it’s ‘1’, change it to ‘0’).

Your task is to find the minimum number of type-2 operations required to make s an alternating binary string. A binary string is alternating if no two adjacent characters are equal.

Approach

The confusing part of this problem is figuring out how to intelligently apply the correct operation at the correct time.

Now here’s the simple step that eliminates all the hassle - if we were to just double the string, we can just use a sliding window of size n to check all possible rotations of the string.

All we need to do then, is just figure out how many flips - or type-2 operations - we need to do to make the current window match either of the two possible alternating strings of length n - one starting with ‘0’ and the other starting with ‘1’.

The easy way of doing this is to just create two template strings of length 2n - one starting with ‘0’ and the other starting with ‘1’ - and then just compare the current window with the corresponding window in the template strings to figure out how many flips we need to do.

And we’re done!

Solution in Python


class Solution:
    def minFlips(self, s: str) -> int:
        N = len(s)
        temp = s + s
        NN = len(temp)

        templateZero = "01" * N
        templateOne = "10" * N

        templateOneIssues = templateZeroIssues = 0
        
        l = 0
        best = inf

        for r in range(NN):
            # new issues
            if temp[r] != templateOne[r]:
                templateOneIssues += 1
            
            if temp[r] != templateZero[r]:
                templateZeroIssues += 1
            
            # clean up of issues no longer within current window
            if r - l + 1 > N:
                if temp[l] != templateOne[l]:
                    templateOneIssues -= 1
                
                if temp[l] != templateZero[l]:
                    templateZeroIssues -= 1

                l += 1

                best = min(best, templateOneIssues, templateZeroIssues)

        return best

Complexity

  • Time: $O(n)$
    Since we’re iterating over a string of length 2n and doing O(1) work for each character.

  • Space: $O(n)$
    Since we store two template strings of length 2n.

Mistakes I Made

I had to look up how to do this one :(

And we are done.