1. Description
Given a binary string s of even length, find the fewest character changes needed to make it beautiful. Each change replaces one character with ‘0’ or ‘1’.
A beautiful string can be split into one or more contiguous substrings, each of even length and containing only zeros or only ones.
Return the minimum number of changes.
2. Example
Example 1
Input: s = “1001”
Output: 2
Explanation: Change s[1] to ‘1’ and s[3] to ‘0’, obtaining “1100”. Splitting it into “11” and “00” meets both requirements, and two changes are necessary.
Example 2
Input: s = “10”
Output: 1
Explanation: Change s[1] to ‘1’ to obtain the beautiful string “11”.
Example 3
Input: s = “0000”
Output: 0
Explanation: The original string already qualifies as a single substring, so no changes are needed.
3. Constraints
- 2 <= s.length <= 10$^5$
- s has an even length.
- s[i] is either ‘0’ or ‘1’.
4. Solutions
Greedy
n = str.size()
Time complexity: O(n)
Space complexity: O(1)
| |