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:
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 <= 105s has an even length.s[i] is either '0' or '1'.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.
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.
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.
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.
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.
| Approach | Complexity |
|---|---|
| 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. |
| 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. |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Check Pairs of Adjacent Characters | O(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. |
Minimum Number of Changes to Make Binary String Beautiful | 2 Ways | Leetcode 2914 |codestorywithMIK • codestorywithMIK • 7,896 views views
Watch 9 more video solutions →Practice Minimum Number of Changes to Make Binary String Beautiful with our built-in code editor and test cases.
Practice on FleetCode