Minimum Changes to Make Alternating Binary String

Easy
635.

Minimum Changes to Make Alternating Binary String

Minimum Changes to Make Alternating Binary String is an easy coding problem on strings and greedy, asked in Amazon, TCS and Capgemini interviews.

A binary string is alternating when no two adjacent characters are equal — "0101" and "1010" are alternating, "0100" is not.

One operation flips a single character. Return the minimum number of operations that makes s alternating.

Example 1

Input
s = "0100"
Output
1
Explanation
Flipping the last character gives "0101".

Example 2

Input
s = "10"
Output
0
Explanation
Already alternating.

Example 3

Input
s = "1111"
Output
2
Explanation
"1010" and "0101" each need two flips.

Constraints

  • 1 <= s.length <= 100000
  • s[i] is '0' or '1'.
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {string} s
 * @return {number}
 */
var minOperationsAlternating = function(s) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Minimum Changes to Make Alternating Binary String — Solution

Minimum Changes to Make Alternating Binary String solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript.

Minimum Changes to Make Alternating Binary String is an easy coding problem on strings and greedy, asked in Amazon, TCS and Capgemini interviews.

  • Difficulty: Easy
  • Topics: Strings, Greedy
  • Asked at: Amazon, TCS, Capgemini
  • Time limit: 2 s
  • Memory limit: 256 MB
  • Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby

Problem statement

A binary string is alternating when no two adjacent characters are equal — "0101" and "1010" are alternating, "0100" is not.

One operation flips a single character. Return the minimum number of operations that makes s alternating.

Example 1

Input: s = "0100"
Output: 1
Explanation: Flipping the last character gives "0101".

Example 2

Input: s = "10"
Output: 0
Explanation: Already alternating.

Example 3

Input: s = "1111"
Output: 2
Explanation: "1010" and "0101" each need two flips.

Constraints

  • 1 <= s.length <= 100000
  • s[i] is '0' or '1'.

Hints for Minimum Changes to Make Alternating Binary String

  1. Hint 1

    An alternating string of a given length is fully determined by its first character — there are exactly two targets.

  2. Hint 2

    Count the mismatches against the pattern that starts with '0'.

  3. Hint 3

    The mismatches against the other pattern are whatever is left over.

How to solve Minimum Changes to Make Alternating Binary String

There are only two alternating strings of length n: the one starting with '0' and the one starting with '1'. They disagree at every position, so mismatches against one are exactly the complement of mismatches against the other.

Approach

  1. Sweep the string, counting positions where s[i] differs from i % 2 == 0 ? '0' : '1'.
  2. Call that count a; the other target needs n - a flips.
  3. Return min(a, n - a).

Why it works

The two targets are bitwise complements, so a position matching one necessarily mismatches the other. Counting once therefore gives both answers, and the minimum of the pair is optimal because no third alternating target exists.

Complexity

  • Time — O(n)
  • Space — O(1)

Pitfalls

  • Fixing violations greedily left to right can overcount — it commits to whichever target the first character suggests.
  • Counting both patterns in separate passes is correct but does twice the work for no reason.

Reference solution

Python

def minOperationsAlternating(s: str) -> int:
    a = 0
    for i, c in enumerate(s):
        want = "0" if i % 2 == 0 else "1"
        if c != want:
            a += 1
    return min(a, len(s) - a)

Java

public static int minOperationsAlternating(String s) {
    int a = 0;
    for (int i = 0; i < s.length(); i++) {
        char want = i % 2 == 0 ? '0' : '1';
        if (s.charAt(i) != want) a++;
    }
    return Math.min(a, s.length() - a);
}

C++

int minOperationsAlternating(string s) {
    int a = 0;
    for (int i = 0; i < (int) s.size(); i++) {
        char want = i % 2 == 0 ? '0' : '1';
        if (s[i] != want) a++;
    }
    return min(a, (int) s.size() - a);
}

JavaScript

var minOperationsAlternating = function(s) {
    var a = 0;
    for (var i = 0; i < s.length; i++) {
        var want = i % 2 === 0 ? "0" : "1";
        if (s.charAt(i) !== want) a++;
    }
    return Math.min(a, s.length - a);
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 515 strings problems · the whole catalogue

Learn the technique: Strings · Greedy Algorithms