1758. Minimum Changes To Make Alternating Binary String

String
Greedy

TIME

O(n)

SPACE

O(1)

Intuition

An alternating binary string can only have two valid patterns:

Start with '0': 010101...
Start with '1': 101010...

Count mismatches for both patterns and return the minimum.

Solution

Pattern 1 (starting with '0'):

Index i even → expected '0'
Index i odd → expected '1'

Pattern 2 (starting with '1'):

Index i even → expected '1'
Index i odd → expected '0'

Count how many characters differ from each pattern in a single pass. The answer is the minimum of the two counts.

Key insight: If a character mismatches pattern 1, it matches pattern 2, and vice versa. So change_start0 + change_start1 = n.

Complexity

Time: O(n), single pass through the string
Space: O(1), only two counters

Edge Cases

Already alternating → return 0
All same characters → return n/2
Single character → return 0

Code

class Solution:
    def minOperations(self, s: str) -> int:
        """
        1758. Minimum Changes To Make Alternating Binary String
        Time: O(n)
        Space: O(1)
        """
        change_start0 = 0
        change_start1 = 0

        for i, ch in enumerate(s):
            if i % 2 == 0:
                if ch != '0':
                    change_start0 += 1
                if ch != '1':
                    change_start1 += 1
            else:
                if ch != '1':
                    change_start0 += 1
                if ch != '0':
                    change_start1 += 1

        return min(change_start0, change_start1)

/**
 * 1758. Minimum Changes To Make Alternating Binary String
 * Time: O(n)
 * Space: O(1)
 */
class Solution {
    public int minOperations(String s) {
        int changeStart0 = 0;
        int changeStart1 = 0;

        for (int i = 0; i < s.length(); i++) {
            char ch = s.charAt(i);

            if (i % 2 == 0) {
                if (ch != '0') changeStart0++;
                if (ch != '1') changeStart1++;
            } else {
                if (ch != '1') changeStart0++;
                if (ch != '0') changeStart1++;
            }
        }

        return Math.min(changeStart0, changeStart1);
    }
}