Problem Statement in English

You’re given a binary string s. You have to find the minimum number of changes required to make the string alternating. A string is called alternating if no two adjacent characters are equal.

Return the minimum number of changes required.

Approach

There are only two possible alternating strings that can be formed from a binary string. One starts with 0 and the other starts with 1.

We can calculate the number of changes required to convert the given string to both of these alternating strings and return the minimum of the two.

And we’re done!

Solution in Python


class Solution:
    def minOperations(self, s: str) -> int:
        n = len(s)

        startingWithZero = 0
        for i in range(len(s)):
            if i % 2:
                if s[i] != "1":
                    startingWithZero += 1
            else:
                if s[i] != "0":
                    startingWithZero += 1

        startingWithOne = 0
        for i in range(len(s)):
            if i % 2:
                if s[i] != "0":
                    startingWithOne += 1
            else:
                if s[i] != "1":
                    startingWithOne += 1


        return min(startingWithZero, startingWithOne)

Complexity

  • Time: $O(n)$
    Since we’re iterating through the string twice.

  • Space: $O(1)$
    Since we’re using only a constant amount of extra space.

And we are done.