Minimum Number of Changes to Make Binary String Beautiful

Problem Description

Given an even-length 0-indexed binary string s, your task is to determine the minimum number of character changes required to make s "beautiful." A string is defined as beautiful if it can be partitioned into one or more substrings where each substring has an even length and consists entirely of 0's or entirely of 1's. In each change, you can flip a character from '0' to '1' or vice versa.

Key Insights

• Since the string length is even, we can always partition it into consecutive pairs.
• For any pair of characters, to form a valid even-length uniform substring, both characters in the pair must be identical.
• For each pair, if the two characters differ, one change is required (either one of the two can be flipped) to make them identical.
• The minimum number of changes is thus the number of mismatched pairs in the string.

Space and Time Complexity

Time Complexity: O(n), where n is the length of the string, since we iterate through the string in steps of 2. Space Complexity: O(1), as only a constant amount of extra space is used.

Solution

The solution is based on the observation that the optimal way to partition the string is into consecutive pairs. For each pair, check if the two characters are the same. If they are different, increment the count of required changes by 1. This greedy approach ensures that every pair is corrected independently, leading to the overall minimum changes required.

Data Structures Used:

• Basic variables for counting and indexing.

Algorithmic Approach:

1. Initialize a counter to 0.
2. Loop through the string in steps of 2.
3. For each pair, if the two characters are different, increment the counter.
4. Return the counter as the minimum number of changes.

Key Gotchas:

• Ensure that the string length is even.
• Process exactly two characters at a time, since the partition must be into even-length substrings.

Code Solutions