Minimum Changes To Make Alternating Binary String - Leetcode Solution

Problem Statement

A binary string is alternating if every two adjacent characters are different. For example, the strings "010" and "1010" are alternating, while the string "110" is not.

You are given a binary string s consisting of n characters. You can perform two types of operations on s:

• Change the i-th character of s to '0' or '1'.
• Swap the i-th and (i+1)-th characters of s. This operation can only be performed if i = 1, 2, ..., n-1.

Return the minimum number of operations needed to make s alternating, or -1 if it is impossible to make s alternating.

Solution

To make s alternating, we need to ensure that no two adjacent characters are the same. Since there are only two possible characters, '0' and '1', we can simply start with one of them, and then alternate between them.

So we try two cases:

1. Start with '0', and alternate between '0' and '1'.
2. Start with '1', and alternate between '1' and '0'.

For each case, we count the number of changes needed to transform s to the alternating string. The answer is the minimum of these two counts.

Note that a swap operation does not change the parity (even/oddness) of the number of adjacent pairs of equal characters. Therefore, if s already has an odd number of adjacent pairs of equal characters, it is impossible to make it alternating with any sequence of operations, and we return -1.

Pseudocode

count_01 = 0
count_10 = 0

for i from 0 to n-2:
    if s[i] == s[i+1]:
        if s[i] == '0':
            count_01 += 1
        else:
            count_10 += 1

if count_01 % 2 == 1 or count_10 % 2 == 1:
    return -1

count_01 = 0
count_10 = 0

for i from 0 to n-1:
    target_01 = '01'[i % 2]
    target_10 = '10'[i % 2]

    if s[i] != target_01:
        count_01 += 1

    if s[i] != target_10:
        count_10 += 1

return min(count_01, count_10)

1