MediumStringUpdated Sep 2026

2914. Minimum Number of Changes to Make Binary String Beautiful

Asked at JPMorgan

Difficulty

Medium

Time

O(n)

Space

O(1)

Pattern

String

Companies

1

Problem

You are given a binary string s (only '0' and '1' characters) whose length is even. A string is called beautiful if you can cut it into one or more pieces so that every piece has an even length and every piece contains only one kind of character (all '0's or all '1's).

You may flip any character to the other bit. Return the minimum number of flips needed to turn s into a beautiful string.

The key observation: any even-length block of equal characters can be split into blocks of length 2. So a string is beautiful exactly when each aligned pair (s[0],s[1]), (s[2],s[3]), ... has two equal characters. The pairs never interact, so you can fix each one on its own.

Cut into even blocks of one character

spair 1pair 210010123The two red characters must be flipped to make eachpair equal
A beautiful string splits into even-length runs of a single bit; here "1100" splits into "11" and "00".

Constraints

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

Examples

Example 1
Inputs = "1001"
Output2
WhyThe aligned pairs are "10" and "01". Both pairs have two different characters, so each needs one flip. Flipping gives "1100", which splits into "11|00".
Example 2
Inputs = "10"
Output1
WhyThere is one pair, "10", and its two characters differ, so one flip is needed. Changing it to "11" makes the whole string one valid block.
Example 3
Inputs = "0000"
Output0
WhyThe pairs are "00" and "00". Both are already equal, so the string is beautiful as is.

Asked At

1 companies
CompanyDifficulty
JPMorganMediumView all JPMorgan questions →

How to Think About It

1

Any even-length block of equal characters can be cut into pairs of length 2. So a string is beautiful iff every aligned pair (s[0],s[1]), (s[2],s[3]), ... has equal characters.

2

Key insight: pairs are independent. A pair with different characters needs exactly one flip; a matching pair needs none.

3

So the answer is the number of indices i (even) where s[i] != s[i+1].

4

Walkthrough for "1001": pairs 10 and 01 both mismatch -> 2 changes (for example to "1100").

5

No DP is needed — the aligned-pair observation removes all interaction between choices.

Optimal Approach

Step 1: changes = 0.
Step 2: For i in 0, 2, 4, ...: if s[i] != s[i+1], changes += 1.
Step 3: Return changes.

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

Check each aligned pair

s10 mismatch10010123iPair "10" differs, so add 1 to the answers01 mismatch10010123iPair "01" also differs, so add 1 more — total is 2answer = count of i where s[i] != s[i+1]i = 0, 2, 4, ...
Only the two characters inside a pair matter; different pairs never affect each other.
ComplexityTime O(n)Space O(1)We scan the string once in steps of two, and only a counter is stored.

What Trips People Up in Real Interviews

1

Setting up a DP over partition points. Explain why aligned pairs are enough, and the problem becomes trivial.

2

Checking unaligned pairs like (s[1], s[2]). Only positions (2k, 2k+1) matter.

3

Counting two flips per mismatched pair. One flip makes the pair equal.

4

Trying to minimize the number of blocks — the question is only about flips.

Solution Code

O(n) time
def minChanges(s):
    return sum(1 for i in range(0, len(s), 2) if s[i] != s[i + 1])

Pro at DSA?

Test your skills with a real FAANG-style mock interview.

Start a Mock Interview →

Frequently Asked Questions

What is the Minimum Number of Changes to Make Binary String Beautiful problem?

Minimum Number of Changes to Make Binary String Beautiful asks for the fewest bit flips so an even-length binary string can be split into substrings of even length that each contain only 0s or only 1s. It looks like a partitioning problem, but it collapses to checking fixed pairs.

How do you solve Minimum Number of Changes to Make Binary String Beautiful?

The optimal approach runs in O(n) time and O(1) space. Scroll up to "Optimal Approach" for the step-by-step walkthrough, diagrams, and code in Python, C++ and Java.

What companies ask Minimum Number of Changes to Make Binary String Beautiful?

Minimum Number of Changes to Make Binary String Beautiful is asked at JPMorgan. It is a medium difficulty problem.

What are common mistakes on Minimum Number of Changes to Make Binary String Beautiful?
  • Setting up a DP over partition points. Explain why aligned pairs are enough, and the problem becomes trivial.
  • Checking unaligned pairs like `(s[1], s[2])`. Only positions `(2k, 2k+1)` matter.
  • Counting two flips per mismatched pair. One flip makes the pair equal.
  • Trying to minimize the number of blocks — the question is only about flips.