2914. Minimum Number of Changes to Make Binary String Beautiful
- String
TIME
O(n)
SPACE
O(1)
Intuition
The partition rule looks like it needs a DP over block boundaries, but it collapses to something local. Cut the string into aligned pairs (s[0], s[1]), (s[2], s[3]), ....
- If the string is beautiful, every block starts at an even index (all earlier blocks have even length) and has even length. So no aligned pair crosses a block boundary, and both characters of each pair sit in the same single-character block. Every pair is equal.
- If every pair is equal, make each pair its own block of length 2. That is a valid partition.
So "beautiful" means exactly "every aligned pair is 00 or 11". The pairs don't interact, and a mismatched pair (01 or 10) needs exactly one change, since changing either character fixes it.
Approach
- Walk
i = 0, 2, 4, .... - Count the pairs with
s[i] != s[i + 1]. - Return the count.
Complexity
- Time: O(n)
- Space: O(1)
Edge Cases
- Already beautiful (example 3): every pair matches, answer 0
- Length 2: the answer is 0 or 1
- Unaligned runs like
"0110": the pairs are01and10, so the answer is 2. Looking at runs instead of aligned pairs would suggest the middle11already fits and get this wrong - Alternating
"0101...": every pair mismatches, so the answer isn / 2
Code
class Solution:
def minChanges(self, s: str) -> int:
"""
2914. Minimum Number of Changes to Make Binary String Beautiful
Time: O(n)
Space: O(1)
"""
# Beautiful <=> every aligned pair (s[2i], s[2i+1]) is equal, and each
# mismatched pair costs exactly one change.
return sum(s[i] != s[i + 1] for i in range(0, len(s), 2))/**
* 2914. Minimum Number of Changes to Make Binary String Beautiful
* Time: O(n)
* Space: O(1)
*/
class Solution {
public int minChanges(String s) {
// Beautiful <=> every aligned pair (s[2i], s[2i+1]) is equal, and each
// mismatched pair costs exactly one change.
int changes = 0;
for (int i = 0; i < s.length(); i += 2) {
if (s.charAt(i) != s.charAt(i + 1)) {
changes++;
}
}
return changes;
}
}