Minimum Changes To Make Alternating Binary String

Minimum Changes To Make Alternating Binary String - Problem

String Easy

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 vice versa.

The string is called alternating if no two adjacent characters are equal. For example, the string "010" is alternating, while the string "0100" is not.

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

Input & Output

Example 1 — Basic Case

$ Input: s = "0010"

› Output: 1

💡 Note: We can change s[1] = '0' to '1' to get "0110", but this isn't alternating. Better: change s[1] to '1' to get "0110" (not alternating) OR change s[2] to '0' to get "0000" (not alternating). Actually, to make "0010" alternating: Pattern "0101" needs 1 change at position 1, Pattern "1010" needs 3 changes. Minimum is 1.

Example 2 — Already Alternating

$ Input: s = "010"

› Output: 0

💡 Note: String is already alternating (0-1-0), so no changes needed.

Example 3 — All Same Characters

$ Input: s = "1111"

› Output: 2

💡 Note: To make alternating: Pattern "0101" needs 4 changes, Pattern "1010" needs 2 changes. Minimum is 2.

Constraints

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

Visualization

Tap to expand

Understanding the Visualization

Input String

Binary string that may not be alternating

Compare Patterns

Check against both possible alternating patterns

Minimum Changes

Return the smaller number of changes needed

Key Takeaway

🎯 Key Insight: Only two alternating patterns exist - compare against both and take the minimum

Asked in

G Google 15 f Facebook 12 M Microsoft 8

The key insight is that only two alternating patterns exist: starting with 0 (0101...) or starting with 1 (1010...). We count mismatches for both patterns and return the minimum. Best approach is the optimized single-pass solution. Time: O(n), Space: O(1)

Common Approaches

Approach	Time	Space	Notes
✓ Optimized - Single Pass	O(n)	O(1)	Count mismatches for both patterns in one pass without generating pattern strings
Brute Force - Try All Patterns	O(n)	O(n)	Generate all possible alternating patterns and find minimum changes

Optimized - Single Pass — Algorithm Steps

Iterate through string once
For each position, check if it matches pattern starting with 0
For each position, check if it matches pattern starting with 1
Count mismatches for both patterns simultaneously
Return minimum count

Visualization

Tap to expand

Step-by-Step Walkthrough

Single Pass

Iterate through string once

Calculate Expected

For each position, determine what both patterns expect

Count Mismatches

Increment counters when actual doesn't match expected

Code -

solution.c — C

#include <stdio.h>
#include <string.h>

int solution(char* s) {
    int n = strlen(s);
    int changes0 = 0; // Changes if pattern starts with '0'
    int changes1 = 0; // Changes if pattern starts with '1'
    
    for (int i = 0; i < n; i++) {
        // Pattern 0: even positions are '0', odd positions are '1'
        char expected0 = (i % 2 == 0) ? '0' : '1';
        if (s[i] != expected0) {
            changes0++;
        }
        
        // Pattern 1: even positions are '1', odd positions are '0'
        char expected1 = (i % 2 == 0) ? '1' : '0';
        if (s[i] != expected1) {
            changes1++;
        }
    }
    
    return (changes0 < changes1) ? changes0 : changes1;
}

int main() {
    char s[100001];
    fgets(s, sizeof(s), stdin);
    s[strcspn(s, "\n")] = 0;  // Remove newline
    
    int result = solution(s);
    printf("%d\n", result);
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n)

Single pass through string of length n

✓ Linear Growth

Space Complexity

O(1)

Only using counter variables, no extra arrays

✓ Linear Space

28.5K Views

Medium Frequency

~15 min Avg. Time

892 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Optimized - Single Pass — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler