Minimum Changes to Make Alternating Binary String — Easy Problem & Solution

Problem statement

A binary string is alternating when no two adjacent characters are equal — "0101" and "1010" are alternating, "0100" is not.

One operation flips a single character. Return the minimum number of operations that makes s alternating.

Example 1

Input: s = "0100"
Output: 1
Explanation: Flipping the last character gives "0101".

Example 2

Input: s = "10"
Output: 0
Explanation: Already alternating.

Example 3

Input: s = "1111"
Output: 2
Explanation: "1010" and "0101" each need two flips.

Constraints

• 1 <= s.length <= 100000
• s[i] is '0' or '1'.

How to solve Minimum Changes to Make Alternating Binary String

There are only two alternating strings of length n: the one starting with '0' and the one starting with '1'. They disagree at every position, so mismatches against one are exactly the complement of mismatches against the other.

Approach

1. Sweep the string, counting positions where s[i] differs from i % 2 == 0 ? '0' : '1'.
2. Call that count a; the other target needs n - a flips.
3. Return min(a, n - a).

Why it works

The two targets are bitwise complements, so a position matching one necessarily mismatches the other. Counting once therefore gives both answers, and the minimum of the pair is optimal because no third alternating target exists.

Complexity

• Time — O(n)
• Space — O(1)

Pitfalls

• Fixing violations greedily left to right can overcount — it commits to whichever target the first character suggests.
• Counting both patterns in separate passes is correct but does twice the work for no reason.

Reference solution

Python

def minOperationsAlternating(s: str) -> int:
    a = 0
    for i, c in enumerate(s):
        want = "0" if i % 2 == 0 else "1"
        if c != want:
            a += 1
    return min(a, len(s) - a)

JavaScript

var minOperationsAlternating = function(s) {
    var a = 0;
    for (var i = 0; i < s.length; i++) {
        var want = i % 2 === 0 ? "0" : "1";
        if (s.charAt(i) !== want) a++;
    }
    return Math.min(a, s.length - a);
};

Also on the editorial tab: C, C#, C++, Go, Java, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

More strings problems

• Find the Original Typed String I Easy
• Rearrange Characters to Make Target String Easy
• Number of Strings That Appear as Substrings in Word Easy
• Circular Sentence Easy
• Number of Senior Citizens Easy
• Find Words Containing Character Easy