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
- The final balanced string has the form
bbb...aaa..., so the deleted characters are theas before the cut plus thebs after the cut. - Sweep left to right tracking
b_count(thebs seen so far) anddp(the best deletions for the prefix). - On a
b, incrementb_count(keeping it costs nothing yet). - On an
a, either delete thisa(dp + 1) or delete everybbefore 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 precedingbs is cheaper. - Tracking only the running
bcount: the DP state must combine both options on eacha. - 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.