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

Solution Approach

Find the minimum number of character flips to make a binary string alternate between 0 and 1. There are only two possible alternating patterns starting with 0 or 1. Count mismatches against both patterns and return the minimum. For each position i, the expected character for pattern-0 is '0' if i is even and '1' if i is odd. Count positions where s[i] differs from this pattern, then the second pattern's flips are n minus the first count.

function minFlips(s) {
  var flips = 0;
  for (var i = 0; i < s.length; i++) {
    var expected = i % 2 === 0 ? '0' : '1';
    if (s[i] !== expected) flips++;
  }
  return Math.min(flips, s.length - flips);
}

Starting pattern-0 assumes the string begins with '0'. The other pattern (starting with '1') is the complement, so its flip count is simply total length minus the first count. Returning the minimum of the two gives the answer.

Time complexity is O(n), space complexity is 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);
    }
}