#1653

Medium

auto_awesomeState transition dynamic programming

LeetCode Problem Workspace

Minimum Deletions to Make String Balanced

Determine the minimum number of deletions to transform a string of 'a' and 'b' into a balanced order using DP.

Problem Statement

Given a string s containing only 'a' and 'b', delete characters to ensure the string is balanced. A string is balanced if no 'b' occurs before an 'a'.

Return the minimum number of deletions required to achieve this balance. For example, given s = "aababbab", the minimum deletions needed are 2 to reorder it into a fully balanced string.

Examples

Example 1

Input: s = "aababbab"

Output: 2

You can either: Delete the characters at 0-indexed positions 2 and 6 ("aababbab" -> "aaabbb"), or Delete the characters at 0-indexed positions 3 and 6 ("aababbab" -> "aabbbb").

Example 2

Input: s = "bbaaaaabb"

Output: 2

The only solution is to delete the first two characters.

Constraints

1 <= s.length <= 105
s[i] is 'a' or 'b'.

Solution Approach

Dynamic Programming State Transition

Track the minimum deletions needed at each index using a DP array. For each character, either delete it or account for previous 'b's to maintain balance.

Counting Preceding Bs and Following As

Maintain a running count of 'b's seen so far and 'a's remaining. At each index, the minimum deletions is either deleting the current 'b' or the remaining 'a's after it.

Optimized One-Pass Calculation

Use a single pass with two counters instead of full DP array to track deletions. Incrementally update minimum deletions by comparing current 'b' deletions versus future 'a' deletions.

Complexity Analysis

Metric	Value
Time	O(n)
Space	O(1)

Time complexity is O(n) because we process each character once. Space complexity is O(1) using counters instead of full DP storage.

What Interviewers Usually Probe

You may ask how to handle 'b's before 'a's efficiently using dynamic programming.
They may hint at optimizing the DP array to constant space with counters.
Expect discussion on trade-offs between deleting 'a's versus 'b's at each index.

Common Pitfalls or Variants

Common pitfalls

Failing to count all 'a's after the current index leads to incorrect deletions.
Trying a full DP array without realizing a simple counter can suffice.
Misinterpreting balance conditions and deleting unnecessary characters.

Follow-up variants

Compute minimum insertions instead of deletions to achieve balance.
Handle strings with multiple character types and define custom order rules.
Return the actual balanced string, not just the count of deletions.

FAQ

What is the core idea behind Minimum Deletions to Make String Balanced?

It involves deleting characters to ensure no 'b' occurs before an 'a', using a state transition dynamic programming approach.

Can this problem be solved in one pass?

Yes, by maintaining counters for preceding 'b's and remaining 'a's, you can compute minimum deletions in a single pass.

Why not delete all 'a's or all 'b's?

Deleting all of one character type is rarely optimal; the goal is minimal deletions using careful index tracking.

How does the DP state transition work here?

At each index, choose the smaller between deleting the current 'b' or deleting remaining 'a's to maintain balance.

Is extra space required for DP?

No, you can optimize to O(1) space with two counters instead of storing a full DP array.

terminal

Solution

Solution 1: Dynamic Programming

We define $f[i]$ as the minimum number of characters to be deleted in the first $i$ characters to make the string balanced. Initially, $f[0]=0$. The answer is $f[n]$.

1

2

3

4

5

6

7

8

9

10

11

12

class Solution:
    def minimumDeletions(self, s: str) -> int:
        n = len(s)
        f = [0] * (n + 1)
        b = 0
        for i, c in enumerate(s, 1):
            if c == 'b':
                f[i] = f[i - 1]
                b += 1
            else:
                f[i] = min(f[i - 1] + 1, b)
        return f[n]

Solution 2: Enumeration + Prefix Sum

We can enumerate each position $i$ in the string $s$, dividing the string $s$ into two parts, namely $s[0,..,i-1]$ and $s[i+1,..n-1]$. To make the string balanced, the number of characters we need to delete at the current position $i$ is the number of character 'b' in $s[0,..,i-1]$ plus the number of character 'a' in $s[i+1,..n-1]$.

1

2

3

4

5

6

7

8

9

10

11

12

class Solution:
    def minimumDeletions(self, s: str) -> int:
        n = len(s)
        f = [0] * (n + 1)
        b = 0
        for i, c in enumerate(s, 1):
            if c == 'b':
                f[i] = f[i - 1]
                b += 1
            else:
                f[i] = min(f[i - 1] + 1, b)
        return f[n]

Continue Practicing

#1896 minimum cost to change the final value of expression #2019 the score of students solving math expression #678 valid parenthesis string