NeetCode #785LC-2914MediumGreedy
← Back to All Problems#785 · #2914 · Minimum Number of Changes to Make Binary String Beautiful(使二进制字符串变美丽的最少修改次数)
📌 Problem Statement & Constraints
Given an even-length binary string
s, it is beautiful if it can be split into one or more even-length substrings, each with an equal number of 0s and 1s. Return the minimum number of character changes to make s beautiful. Constraints: 2 <= s.length <= 10^5, s.length is even, s consists of 0 and 1.💡 Core Algorithmic Approaches
- A substring of even length with equal zeros and ones is exactly a balanced block.
- The finest such split is into adjacent pairs, which is always achievable for even-length strings.
- In each pair
(s[2i], s[2i+1]), if the two characters are equal the pair is unbalanced and needs one change. - Summing one change per unbalanced pair gives the minimum, since any coarser split can only need at least as many changes.
💻 Benchmark Python3 Implementation
class Solution:
def minChanges(self, s: str) -> int:
res = 0
for i in range(0, len(s), 2):
if s[i] == s[i + 1]: # pair is 00 or 11 -> one change
res += 1
return res⚡ Complexity Deep Dive
⏱️ Time Complexity
O(n): a single pass over the pairs.
💾 Space Complexity
O(1): one counter.
⚠️ Interview Pitfalls & Follow-ups
- Counting unequal pairs: a pair like
01is already balanced and needs no change. - Trying to build longer substrings: the pair split is optimal and simpler.
- Forgetting that the length is even: the pairing is only well defined because of this guarantee.
- Changing both characters of a pair: one change always suffices to balance a pair.
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.