Editorial

Solution walkthrough

Review the explanation, then compare the reference implementation.

Video explanation

Solution

Intuition

Once an alternating string's first bit is chosen, every other bit is forced. There are only two possible target strings: one starting with zero and one starting with one. Each mismatch with a target requires exactly one change.

Approach

Scan the input against an expected bit initially zero, counting mismatches and toggling the expectation after every character. Repeat with an initial one. Return the smaller count. This examines both possible valid results without constructing them, and a one-character string has answer zero because it already matches one of the two patterns.

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

        for c in s:
            if c != t:
                curr += 1
            t = '1' if t == '0' else '0'

        res = curr
        t = '1'
        curr = 0

        for c in s:
            if c != t:
                curr += 1
            t = '1' if t == '0' else '0'

        return min(res, curr)

Complexity analysis

Let n = s.length. Time: O(n) across two scans. Auxiliary space: O(1).