Problem Description
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 and 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.
Key Insights
- Each beautiful substring must consist of the same character.
- Substrings must have an even length.
- Count the number of changes needed to convert alternating groups of characters into uniform groups of the same character.
- The number of changes required depends on the length of the groups of '0's and '1's.
Space and Time Complexity
Time Complexity: O(n)
Space Complexity: O(1)
Solution
To solve the problem, we can iterate through the string and count the number of changes needed to group the characters into beautiful substrings. The algorithm involves iterating through the string in pairs, checking if both characters are the same. If they are different, we need to change one of them, which counts as a change. The approach uses a linear scan of the string while maintaining a counter for the number of changes required.