⚡Flashcard Drill➔
NeetCode #803LC-1653MediumGreedy
← Back to All Problems

#803 · #1653 · Minimum Deletions to Make String Balanced(使字符串平衡的最少删除次数)

📌 Problem Statement & Constraints

You are given a string s of a and b. A string is balanced if no a appears after a b. In one deletion you may remove any character. Return the minimum deletions to make s balanced. Constraints: 1 <= s.length <= 10^5.

💡 Core Algorithmic Approaches

  1. The final balanced string has the form bbb...aaa..., so the deleted characters are the as before the cut plus the bs after the cut.
  2. Sweep left to right tracking b_count (the bs seen so far) and dp (the best deletions for the prefix).
  3. On a b, increment b_count (keeping it costs nothing yet).
  4. On an a, either delete this a (dp + 1) or delete every b before it (b_count); take the minimum.

💻 Benchmark Python3 Implementation

class Solution:
    def minimumDeletions(self, s: str) -> int:
        res = 0
        b_count = 0
        for c in s:
            if c == "b":
                b_count += 1
            else:                      # 'a'
                res = min(res + 1, b_count)
        return res

⚡ Complexity Deep Dive

⏱️ Time Complexity
O(n): a single pass.
💾 Space Complexity
O(1): two counters.

⚠️ Interview Pitfalls & Follow-ups

  • Deleting all as unconditionally: sometimes deleting the preceding bs is cheaper.
  • Tracking only the running b count: the DP state must combine both options on each a.
  • Forgetting that the cut can be anywhere: the sweep considers every prefix cut implicitly.
  • Assuming the answer is min(countA, countB): that ignores the ordering constraint.
⚡
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