Code Logo

Minimum Changes to Make Alternating Binary String

Published at24 Jul 2026
Created by
Easy 0 views
Like0

Given a binary string s containing only 0s and 1s, you can flip any character from 0 to 1 or 1 to 0. Return the minimum number of flips needed to make the string alternating, meaning no two adjacent characters are equal.

An alternating binary string has exactly two possible patterns: starting with 0 (0101...) or starting with 1 (1010...). The DP approach computes mismatches for both patterns in a single pass and returns the minimum.

For pattern 0, even indices should be '0' and odd indices should be '1'. For pattern 1, the opposite applies. By iterating through the string once and counting mismatches for both patterns simultaneously, we get the total flips needed for each pattern in O(n) time.

This is a 2-state DP that uses two counters and O(1) space. No array is needed because the expected character at each position depends only on the index parity and the chosen pattern.

Edge cases include empty string (return 0), single character (always alternating, return 0), and already alternating strings (one pattern will have zero mismatches).

The two-pattern comparison approach demonstrates that some DP problems have a small, fixed number of possible states. By explicitly representing both valid final states, we can compute the minimum edit distance to either one without explicitly storing the intermediate results.

Example Input & Output

Example 1
Input
""
Output
0
Explanation

Empty.

Example 2
Input
"1111"
Output
2
Explanation

To "1010" or "0101" both need 2 flips.

Example 3
Input
"0100"
Output
1
Explanation

Change last char to 1: "0101".

Example 4
Input
"10"
Output
0
Explanation

Already alternating.

Example 5
Input
"1"
Output
0
Explanation

Single char.

Algorithm Flow

Recommendation Algorithm Flow for Minimum Changes to Make Alternating Binary String
Recommendation Algorithm Flow for Minimum Changes to Make Alternating Binary String

Solution Approach

Count mismatches for both patterns (0-start and 1-start) in one pass. Return the minimum.

function solution(s) {
  var c0=0,c1=0;
  for (var i=0;i<s.length;i++) {
    if (i%2===0) {
      if (s.charAt(i)!=='0') c0++;
      if (s.charAt(i)!=='1') c1++;
    } else {
      if (s.charAt(i)!=='1') c0++;
      if (s.charAt(i)!=='0') c1++;
    }
  }
  return Math.min(c0,c1);
}

Time O(n), Space O(1).

Best Answers

java
class Solution {
    public int solution(String s) {
        int c0=0,c1=0;
        for (int i=0;i<s.length();i++) {
            char ch=s.charAt(i);
            if (i%2==0) {
                if (ch!='0') c0++;
                if (ch!='1') c1++;
            } else {
                if (ch!='1') c0++;
                if (ch!='0') c1++;
            }
        }
        return Math.min(c0,c1);
    }
}