⚡Flashcard Drill➔
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

  1. A substring of even length with equal zeros and ones is exactly a balanced block.
  2. The finest such split is into adjacent pairs, which is always achievable for even-length strings.
  3. In each pair (s[2i], s[2i+1]), if the two characters are equal the pair is unbalanced and needs one change.
  4. 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 01 is 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.
🎯 Drill This Card Now➔

🧩 Related Greedy Problems