Minimum Changes To Make Alternating Binary String

The idea behind this problem is to count the number of characters that need to be flipped in order to make the string alternating. We have two scenarios for an alternating string: it either starts with ‘0’ or it starts with ‘1’. We count the number of flips required for each case and then return the minimum of the two counts.

Python solution:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10

class Solution:
    def minOperations(self, s: str) -> int:
        s1, s2 = ['0', '1']*len(s), ['1', '0']*len(s)
        count1, count2 = 0, 0
        for i in range(len(s)):
            if s[i] != s1[i]:
                count1 += 1
            if s[i] != s2[i]:
                count2 += 1
        return min(count1, count2)

In this code:

  • We first create two expected strings s1 and s2 of the same length as s. s1 starts with ‘0’ and s2 starts with ‘1’.

  • We then initialize two counters count1 and count2 to count the number of characters that need to be flipped to match s1 and s2, respectively.

  • We iterate over the characters in s and compare them with the corresponding characters in s1 and s2. If a character does not match, we increment the corresponding counter.

  • Finally, we return the minimum of count1 and count2 which gives us the minimum number of operations needed to make s alternating.

The greedy approach is about choosing the best option at each step with the hope that these local optimums will lead to a global optimum. In our context, the greedy choice is about minimizing the flips at each character position. We don’t look ahead to see how a choice will affect the future; we simply make the choice that seems best at the current step.

The Counter is used to count the discrepancies for two possible patterns. We’re making a greedy choice to minimize the number of flips for each pattern at each position.

The high-level concepts used in this problem are:

  1. Python’s Counter to count the number of discrepancies.
  2. The Greedy Algorithm to make the choice that minimizes the number of flips at each step.