Minimum Number of Changes to Make Binary String Beautiful — Medium Problem & Solution

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'.

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])

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#, C++, Go, Java, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

More strings problems

• Make Three Strings Equal Medium
• Number of Ways to Divide a Long Corridor Medium
• Maximum Number of Non-overlapping Palindrome Substrings Medium
• Count Number of Texts Medium
• Delete Characters to Make Fancy String Medium
• Count Number of Homogenous Substrings Medium