What is the time complexity of the Direct Counting Approach?

The time complexity is O(n) where n is the length of the string, as we iterate through the string once.

What is the space complexity of the Optimized Counting Approach?

The space complexity is O(1) as we only use a constant amount of extra space for a single counter.

Why are there only two possible alternating patterns?

For a binary string, there are only two valid alternating patterns: starting with '0' (0101...) or starting with '1' (1010...). Any alternating binary string must match one of these patterns.

How does the optimization work in the second approach?

Since every position matches exactly one of the two patterns, count0 + count1 = n. We only need to count for one pattern and derive the other as n - count0.

Minimum Changes To Make Alternating Binary String

Difficulty: Easy | Acceptance: 67.80% | Paid: No Topics: String

You are given a string s consisting only of the characters ‘0’ and ‘1’. In one operation, you can change any ‘0’ to ‘1’ or ‘1’ to ‘0’.

Return the minimum number of operations needed to make s alternating.

A string is alternating if no two adjacent characters are equal. For example, “0101” and “1010” are alternating, while “0100” is not.

Examples
Constraints
Direct Counting Approach
Optimized Counting Approach

Examples

Input: s = "0100"
Output: 1
Explanation: Change the last character to '1' to get "0101".

Input: s = "10"
Output: 0
Explanation: The string is already alternating.

Input: s = "1111"
Output: 2
Explanation: Change the second and last characters to '0' to get "1010".

Constraints

1 <= s.length <= 10⁴
s[i] is either '0' or '1'.

Direct Counting Approach

Intuition There are only two valid alternating patterns for a binary string: starting with ‘0’ (0101…) or starting with ‘1’ (1010…). We count changes needed for each pattern and return the minimum.

Steps

Initialize two counters for changes needed for both patterns
Iterate through the string and count mismatches for both patterns
For each position, check if character differs from expected value in both patterns
Return the minimum of both counts

python

class Solution:
    def minOperations(self, s: str) -&gt; int:
        n = len(s)
        count0 = 0  # changes needed for pattern starting with '0'
        count1 = 0  # changes needed for pattern starting with '1'
        
        for i in range(n):
            expected0 = '0' if i % 2 == 0 else '1'
            expected1 = '1' if i % 2 == 0 else '0'
            
            if s[i] != expected0:
                count0 += 1
            if s[i] != expected1:
                count1 += 1
        
        return min(count0, count1)

Complexity

Time: O(n) where n is the length of the string
Space: O(1) only using constant extra space
Notes: Simple and straightforward approach with clear logic

Optimized Counting Approach

Intuition We can optimize by noting that count0 + count1 = n (every position matches exactly one of the two patterns). So we only need to count for one pattern and derive the other.

Steps

Count changes needed for pattern starting with ‘0’
The changes for pattern starting with ‘1’ is simply n - count0
Return the minimum of both

python

class Solution:
    def minOperations(self, s: str) -&gt; int:
        n = len(s)
        count0 = 0  # changes needed for pattern starting with '0'
        
        for i in range(n):
            expected = '0' if i % 2 == 0 else '1'
            if s[i] != expected:
                count0 += 1
        
        # count1 = n - count0 (every position matches exactly one pattern)
        return min(count0, n - count0)

Complexity

Time: O(n) where n is the length of the string
Space: O(1) only using constant extra space
Notes: Slightly more efficient as we only track one counter and use mathematical relationship