Skip to main content
Talentd

Minimum Number of Changes to Make Binary String Beautiful - Solution & Explanation

MediumString17 min readAsked at: Microsoft, Meta, Google +1
Practice this problem

Problem Statement

You are given a 0-indexed binary string s having an even length.

A string is beautiful if it's possible to partition it into one or more substrings such that:

  • Each substring has an even length.
  • Each substring contains only 1's or only 0's.

You can change any character in s to 0 or 1.

Return the minimum number of changes required to make the string s beautiful.

 

Example 1:

Input: s = "1001"
Output: 2
Explanation: We change s[1] to 1 and s[3] to 0 to get string "1100".
It can be seen that the string "1100" is beautiful because we can partition it into "11|00".
It can be proven that 2 is the minimum number of changes needed to make the string beautiful.

Example 2:

Input: s = "10"
Output: 1
Explanation: We change s[1] to 1 to get string "11".
It can be seen that the string "11" is beautiful because we can partition it into "11".
It can be proven that 1 is the minimum number of changes needed to make the string beautiful.

Example 3:

Input: s = "0000"
Output: 0
Explanation: We don't need to make any changes as the string "0000" is beautiful already.

 

Constraints:

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

Approach Overview

Problem Overview: You are given a binary string s of even length. A string is considered beautiful if every consecutive pair of characters (s[0], s[1], s[2], s[3], …) contains identical values. The task is to compute the minimum number of character changes required to satisfy this rule.

Approach 1: Check Pairs of Adjacent Characters (O(n) time, O(1) space)

The simplest observation: each pair of positions must contain the same bit. Iterate through the string in steps of two and compare s[i] with s[i+1]. If the two characters differ (01 or 10), one change is required to make them equal. Either character can be flipped, so the minimum cost per mismatched pair is exactly one operation. This approach works because each pair is independent of the others—changing one pair never affects another pair. The algorithm performs a single linear scan and counts mismatches, making it optimal with O(n) time and constant O(1) space.

Approach 2: Using Sliding Window for Efficient Changes (O(n) time, O(1) space)

This approach frames the same idea using a window of size two. Maintain a sliding window over the string and process characters in pairs. For every window [i, i+1], check whether both characters match. If they differ, increment the change counter because one modification is required to make the pair uniform. After evaluating the window, move it forward by two positions to process the next pair. The sliding window interpretation is useful when you are used to solving sliding window problems or when adapting the logic to variations where window size might change. Despite the different framing, the algorithm still performs a single pass over the string.

The key insight is that the beautiful condition operates strictly on fixed-size pairs. No global restructuring or dynamic programming is required. Each pair contributes either 0 changes (if both bits match) or 1 change (if they differ). Because of this independence, a greedy local check produces the optimal result.

This problem mainly tests comfort with basic iteration and pattern recognition in string processing. Many candidates initially overthink it with frequency counts or substring replacements, but the structure of the constraint immediately reduces it to pair comparisons.

Recommended for interviews: Approach 1 is what interviewers typically expect. It shows you recognized the pair independence and implemented the greedy check in a single pass. The sliding window framing is conceptually equivalent but can help demonstrate familiarity with common algorithmic patterns.

Approach 1: Approach 1: Check Pairs of Adjacent Characters

To make the binary string beautiful, we need to ensure that each pair of adjacent characters forms a part of a longer sequence of identical numbers. For instance, if there is '10' or '01', we can choose to change one of the characters to make the pair '11' or '00'. We will count how many changes are needed to make all pairs in the desired format.

Since the string length is even, we can consider every odd index with its preceding even index in the string. We will check how many such pairs would need to be changed either to '00' or '11'. The sum of these changes will be our answer.

The function minChangesToBeautiful takes a binary string as input and computes the number of changes required to make it beautiful by counting adjacent different pairs. For each such pair found, it increments a change counter. This is based on pairing every two consecutive numbers in the string and checking if they are different.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(n), where n is the length of the string. We make a single pass through the string, examining pairs of characters.
Space Complexity: O(1), only a few variables are used for counting.

Try this approach in the editor →

Approach 2: Approach 2: Using Sliding Window for Efficient Changes

This approach utilizes a sliding window that calculates the cumulative changes required to transform each segment of the string into either '00' or '11'. While iterating over pairs of characters, we check the discrepancy from '00' alternations and '11' alternations. To achieve this, two patterns are monitored: one representing making all pairs '00' and the other '11'. The minimum between these two paths will give the total minimum steps needed.

This function monitors two patterns while looping through the string: one where the first character is assumed '0', and one where the first is '1'. By checking against two alternating sequences, it accumulates the minimal set of changes needed against either pattern. The result is the lesser of the two computed totals.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(n), where n is the length of the string, involving one linear iteration over the data.
Space Complexity: O(1), requiring no additional space except variables.

Try this approach in the editor →

Approach 3: Counting

We only need to traverse all odd indices 1, 3, 5, cdots of the string s. If the current odd index is different from the previous index, i.e., s[i] \ne s[i - 1], we need to modify the current character so that s[i] = s[i - 1]. Therefore, the answer needs to be incremented by 1.

After the traversal, we return the answer.

The time complexity is O(n), where n is the length of the string s. The space complexity is O(1).

Code

PythonJavaC++GoTypeScript

Python

Java

C++

Go

TypeScript

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Approach 1: Check Pairs of Adjacent Characters

Time Complexity: O(n), where n is the length of the string. We make a single pass through the string, examining pairs of characters.
Space Complexity: O(1), only a few variables are used for counting.

Approach 2: Using Sliding Window for Efficient Changes

Time Complexity: O(n), where n is the length of the string, involving one linear iteration over the data.
Space Complexity: O(1), requiring no additional space except variables.

Counting—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Check Pairs of Adjacent CharactersO(n)O(1)Best general solution. Simple linear scan with constant memory.
Sliding Window (size 2)O(n)O(1)Useful when applying a consistent sliding-window pattern or adapting to similar problems.

Video Solution

Minimum Number of Changes to Make Binary String Beautiful | 2 Ways | Leetcode 2914 |codestorywithMIK • codestorywithMIK • 8,055 views views

Watch 9 more video solutions →

Frequently Asked Questions

Is Minimum Number of Changes to Make Binary String Beautiful easy or hard?
The problem is categorized as Medium on LeetCode, but the core logic is relatively straightforward once the pair constraint is recognized. Candidates who quickly identify that each pair can be evaluated independently usually solve it in a few lines of code.
Minimum Number of Changes to Make Binary String Beautiful Python/Java solution
In Python or Java, the solution typically loops through the string with a step of two and compares s[i] with s[i+1]. Each mismatch increases the change count by one. This implementation runs in O(n) time and uses constant extra space.
How to solve Minimum Number of Changes to Make Binary String Beautiful in O(n)?
Traverse the string from left to right in steps of two. For each pair (i, i+1), check whether both characters are equal. If they differ, increment the change counter because one modification is needed to make the pair identical. Continue until the end of the string.
What is the best approach for Minimum Number of Changes to Make Binary String Beautiful?
The optimal approach is to iterate through the string in pairs and compare adjacent characters. If a pair like '01' or '10' appears, one change is required to make both characters equal. This greedy observation works because each pair is independent. The algorithm runs in O(n) time and O(1) space.
Is Minimum Number of Changes to Make Binary String Beautiful asked at Google/Amazon/Meta?
String manipulation and greedy pair-check problems similar to this appear frequently in interviews at companies like Amazon, Google, and Meta. While this exact problem may vary, the underlying pattern of analyzing fixed-size groups in a string is common in technical interviews.
What data structure is used in Minimum Number of Changes to Make Binary String Beautiful?
The problem mainly relies on basic string traversal. No complex data structures are required—only simple iteration and character comparison. A counter variable tracks how many pairs require modification.
What is the time complexity of Minimum Number of Changes to Make Binary String Beautiful?
The time complexity is O(n), where n is the length of the binary string. The algorithm scans the string once and evaluates characters in pairs. Space complexity remains O(1) since only a counter variable is needed.

Ready to solve this problem?

Practice Minimum Number of Changes to Make Binary String Beautiful with our built-in code editor and test cases.

Practice on FleetCode
Previous

Longest Substring Without Repeating Characters

Next

Longest Palindromic Substring