Minimum Number of Changes to Make Binary String Beautiful

Medium
1026.

Minimum Number of Changes to Make Binary String Beautiful

Minimum Number of Changes to Make Binary String Beautiful is a medium coding problem on strings and greedy, asked in Amazon, Google and Microsoft interviews.

A binary string of even length is beautiful if it can be split into substrings such that every piece has even length and consists of a single repeated character — all 0s or all 1s.

You may change any character to 0 or 1. Return the minimum number of changes that makes s beautiful.

Example 1

Input
s = "1001"
Output
2
Explanation
Change to `1100` (or `0011`): two edits.

Example 2

Input
s = "10"
Output
1
Explanation
One edit makes it `00` or `11`.

Example 3

Input
s = "0000"
Output
0
Explanation
Already beautiful.

Constraints

  • 2 <= s.length <= 10^5
  • s has an even length.
  • s[i] is either '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 minChanges = function(s) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Minimum Number of Changes to Make Binary String Beautiful Solution

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

Minimum Number of Changes to Make Binary String Beautiful is a medium coding problem on strings and greedy, asked in Amazon, Google and Microsoft interviews.

  • Difficulty: Medium
  • Topics: Strings, Greedy
  • Asked at: Amazon, Google, Microsoft
  • 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 of even length is beautiful if it can be split into substrings such that every piece has even length and consists of a single repeated character — all 0s or all 1s.

You may change any character to 0 or 1. Return the minimum number of changes that makes s beautiful.

Example 1

Input: s = "1001"
Output: 2
Explanation: Change to `1100` (or `0011`): two edits.

Example 2

Input: s = "10"
Output: 1
Explanation: One edit makes it `00` or `11`.

Example 3

Input: s = "0000"
Output: 0
Explanation: Already beautiful.

Constraints

  • 2 <= s.length <= 10^5
  • s has an even length.
  • s[i] is either '0' or '1'.

Hints for Minimum Number of Changes to Make Binary String Beautiful

  1. Hint 1

    Any partition into even-length blocks can be refined into blocks of exactly length 2.

  2. Hint 2

    So it is enough to make each fixed pair s[0..1], s[2..3], … uniform.

  3. Hint 3

    A pair whose two characters differ costs exactly one change.

How to solve Minimum Number of Changes to Make Binary String Beautiful

Split s into fixed pairs at indices (0,1), (2,3), … and count the pairs whose two characters differ. Each such pair needs exactly one edit.

Approach

  1. For every even index i, compare s[i] with s[i+1].
  2. Count the mismatches.

Why it works

The key observation is that any even-length block of a single character can be cut into blocks of length two without changing the string, so a string is beautiful exactly when every fixed pair at an even offset is uniform. That collapses a search over partitions into a single independent check per pair, and the pairs cannot interact because the boundaries are fixed at even offsets.

Complexity

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

Pitfalls

  • The pairs start at even indices; sliding a window by one mixes adjacent blocks.
  • Each mismatched pair costs 1, not 2 — changing one of the two characters is enough.
  • The input length is guaranteed even, so there is no trailing odd character.

Reference solution

Python

def minChanges(s: str) -> int:
    return sum(1 for i in range(0, len(s), 2) if s[i] != s[i + 1])

Java

public static int minChanges(String s) {
    int changes = 0;
    for (int i = 0; i + 1 < s.length(); i += 2) {
        if (s.charAt(i) != s.charAt(i + 1)) changes++;
    }
    return changes;
}

C++

int minChanges(string s) {
    int changes = 0;
    for (size_t i = 0; i + 1 < s.size(); i += 2) {
        if (s[i] != s[i + 1]) changes++;
    }
    return changes;
}

JavaScript

var minChanges = function(s) {
    var changes = 0;
    for (var i = 0; i + 1 < s.length; i += 2) {
        if (s.charAt(i) !== s.charAt(i + 1)) changes++;
    }
    return changes;
};

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