Minimum Changes To Make Alternating Binary String

Problem Id: 1758 Difficulty: Easy Tag: Array Tag: Greedy


Intuition

Basically there are only 2 ways to make a string alternating. For example, given a string with length 5, the target string should be either 10101 or 01010.

One improvement of this problem comes from the fact that 2 different numbers of changes can sum up to the length of the string. So we only need to calculate one of them.

Solution


class Solution:
    def minOperations(self, s):
        odd = False
        count = 0
        for c in s:
            if c != ("1" if odd else "0"):
                count += 1
            odd = not odd
        return min(len(s) - count, count)