Classic problem #1653MediumStringDynamic ProgrammingStack
Minimum Deletions to Make String Balanced
Real-world version: Tidying a Line of Two Crate KindsTracked in this browser only
Read Minimum Deletions to Make String Balanced on LeetCode(opens in a new tab)
The statement here is our own: the same inputs, outputs and technique.
A line line holds only the characters a and b. The line is tidy when no b stands anywhere before an a, so every a comes before every b.
Return the fewest characters that have to be removed to leave the line tidy.
Examples
Example 1
- Input
- line = "bab"
- Output
- 1
Removing the single a leaves two b letters, which is tidy. Removing both b letters instead would cost two.
Example 2
- Input
- line = "bbbaaa"
- Output
- 3
Three b letters stand before three a letters, so either all the a letters or all the b letters have to go, and each costs three.
Example 3
- Input
- line = "ab"
- Output
- 0
The line is already tidy, so nothing is removed.
Constraints
- 1 <= line.length <= 10^5
- every character of line is a or b
The signature
The editor starts with this. It matches the parent problem's shape, so a solution that works here works on a standard judge unchanged.
Python
def minimum_deletions(line: str) -> int:Java
public int minimumDeletions(String line)Checking your plan…
How this problem was checked
- Passed: Reference solution run against 15 test cases: 15 passed
- Passed: 3 worked examples confirmed by running the code
- Passed: 0 eight-word sequences shared with the parent problem's text
- Passed: Agrees with an independent brute-force solution on random inputs
- Passed: Test set shown to catch deliberately broken solutions
- Passed: Reviewed by a separate quality pass
- Passed: Function arity matches the parent problem's