Problem Description

You have a string s that contains only characters 'a' and 'b'.

A string is considered balanced when there are no positions where a 'b' appears before an 'a'. In other words, for any pair of indices (i,j) where i < j, if s[i] = 'b' and s[j] = 'a', the string is not balanced.

You can delete any number of characters from s to make it balanced. Your task is to find the minimum number of deletions needed to achieve this.

For example:

• The string "aababbab" is not balanced because there are 'b' characters that appear before 'a' characters
• The string "bbbbb" is balanced (all 'b's, no 'a' after any 'b')
• The string "aaaa" is balanced (all 'a's)
• The string "aaabbb" is balanced (all 'a's come before all 'b's)

The goal is to remove the fewest characters possible to ensure no 'b' comes before any 'a' in the resulting string.

Intuition

To make the string balanced, we need to ensure no 'b' appears before any 'a'. Let's think about what happens as we process the string from left to right.

At each position, we need to make a decision based on the current character:

1. If we encounter a 'b': This doesn't create any immediate problem. The string up to this point remains as balanced as it was before, since 'b' can appear at the end without issues.

2. If we encounter an 'a': This is where we face a choice. Any 'b' that appeared before this 'a' creates an imbalance. We have two options:

   • Delete this 'a' to avoid the conflict (cost: 1 deletion)
   • Keep this 'a' but delete all previous 'b's (cost: number of 'b's seen so far)

The key insight is that we want to choose the option with minimum cost at each step.

This naturally leads to a dynamic programming approach where:

• We track the minimum deletions needed to balance the string up to each position
• We maintain a count of 'b's seen so far
• For each 'a', we choose the minimum between deleting it or deleting all previous 'b's

The formula becomes:

• When we see a 'b': f[i] = f[i-1] (no additional deletions needed)
• When we see an 'a': f[i] = min(f[i-1] + 1, b) where b is the count of 'b's seen so far

This greedy choice at each step ensures we find the globally optimal solution with minimum deletions.

Learn more about Stack and Dynamic Programming patterns.

Solution Approach

The solution uses dynamic programming to track the minimum deletions needed at each position.

State Definition:

• f[i] represents the minimum number of deletions needed to make the first i characters balanced
• b counts the number of 'b' characters seen so far

Initialization:

• f[0] = 0 (empty string is balanced)
• b = 0 (no 'b's seen initially)

State Transition: We iterate through the string with index i from 1 to n:

1. When s[i-1] = 'b':

   • The current 'b' doesn't create imbalance
   • f[i] = f[i-1] (no additional deletions)
   • Update b += 1 to track this 'b'

2. When s[i-1] = 'a':

   • Option 1: Delete this 'a' → cost is f[i-1] + 1
   • Option 2: Keep this 'a' and delete all previous 'b's → cost is b
   • f[i] = min(f[i-1] + 1, b)

The state transition equation is:

f[i] = {
    f[i-1],                 if s[i-1] = 'b'
    min(f[i-1] + 1, b),     if s[i-1] = 'a'
}

Implementation Details:

def minimumDeletions(self, s: str) -> int:
    n = len(s)
    f = [0] * (n + 1)  # DP array
    b = 0              # Count of 'b's
  
    for i, c in enumerate(s, 1):  # 1-indexed iteration
        if c == 'b':
            f[i] = f[i - 1]
            b += 1
        else:  # c == 'a'
            f[i] = min(f[i - 1] + 1, b)
  
    return f[n]

Space Optimization: Since each state only depends on the previous state and variable b, we could optimize space to O(1) by using a single variable instead of an array, though the given solution uses O(n) space for clarity.

Time Complexity: O(n) - single pass through the string Space Complexity: O(n) - for the DP array

Example Walkthrough

Let's trace through the string s = "aababbab" to see how the algorithm finds the minimum deletions needed.

Initial Setup:

• String: "aababbab" (length = 8)
• DP array f = [0, 0, 0, 0, 0, 0, 0, 0, 0] (size 9, initialized to 0)
• Counter b = 0 (tracks number of 'b's seen)

Step-by-step Processing:

Detailed Decisions:

• Position 1-2 ('a', 'a'): No 'b's seen yet, so keeping these 'a's costs nothing
• Position 3 ('b'): First 'b' appears, no conflict yet
• Position 4 ('a'): This 'a' comes after 1 'b'. Either delete this 'a' (cost: 1) or delete the previous 'b' (cost: 1). Both equal, choose minimum = 1
• Position 5-6 ('b', 'b'): More 'b's accumulate, no new conflicts
• Position 7 ('a'): This 'a' comes after 3 'b's. Either delete this 'a' (cost: 1+1=2) or delete all 3 previous 'b's (cost: 3). Choose minimum = 2
• Position 8 ('b'): Final 'b', no new conflict

Result: The minimum number of deletions needed is f[8] = 2

Verification: One optimal solution is to delete the two 'a's at positions 4 and 7, leaving "aabbbb" which is balanced (all 'a's before all 'b's).

Solution Implementation

Time and Space Complexity

The time complexity is O(n), where n is the length of the string s. The algorithm iterates through the string once with a single for loop, performing constant-time operations (comparisons, assignments, and min operations) for each character.

The space complexity is O(n), not O(1) as stated in the reference answer. The code creates an array f of size n + 1 to store the dynamic programming states, which requires linear extra space. The variable b uses constant space, but the dominant factor is the array f, making the overall space complexity O(n).

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Misunderstanding the Balance Condition

Pitfall: Many people initially think a balanced string means equal numbers of 'a's and 'b's, or that 'a's and 'b's must alternate. This leads to incorrect solutions that try to balance counts rather than positions.

Correct Understanding: A string is balanced when NO 'b' appears before ANY 'a'. Valid balanced strings include:

• "aaabbb" (all 'a's before all 'b's)
• "aaaa" (only 'a's)
• "bbbb" (only 'b's)
• "" (empty string)

2. Incorrect DP State Definition

Pitfall: Defining the DP state as "minimum deletions to balance the entire string up to index i" without properly tracking what characters can still appear after position i.

Solution: The DP state dp[i] should represent the minimum deletions needed to make the first i characters balanced, considering that any characters can follow after position i.

3. Off-by-One Indexing Errors

Pitfall: Mixing 0-based and 1-based indexing when accessing the string and DP array:

# Incorrect - index mismatch
for i in range(1, n + 1):
    if s[i] == 'b':  # ERROR: s[i] is out of bounds when i = n
        dp[i] = dp[i - 1]

Solution: Use enumerate with proper start value or be consistent with indexing:

# Correct approach 1: enumerate with start=1
for i, char in enumerate(s, 1):
    if char == 'b':
        dp[i] = dp[i - 1]

# Correct approach 2: 0-based indexing throughout
for i in range(n):
    if s[i] == 'b':
        dp[i + 1] = dp[i]

4. Not Considering All Options for 'a' Characters

Pitfall: When encountering an 'a', only considering deletion of that 'a' without realizing you could instead delete all previous 'b's:

# Incorrect - missing the option to delete previous b's
if char == 'a':
    dp[i] = dp[i - 1] + 1  # Only considers deleting the 'a'

Solution: Always consider both options:

if char == 'a':
    # Option 1: Delete this 'a'
    # Option 2: Keep this 'a' and delete all previous 'b's
    dp[i] = min(dp[i - 1] + 1, b_count)

5. Forgetting to Update the 'b' Counter

Pitfall: Forgetting to increment b_count when encountering a 'b' character, leading to incorrect cost calculation for keeping subsequent 'a's:

# Incorrect - forgot to update b_count
if char == 'b':
    dp[i] = dp[i - 1]
    # Missing: b_count += 1

Solution: Always update the counter when seeing a 'b':

if char == 'b':
    dp[i] = dp[i - 1]
    b_count += 1  # Don't forget this!

6. Space Optimization Gone Wrong

Pitfall: Attempting to optimize space to O(1) but incorrectly updating the same variable:

# Incorrect space optimization
def minimumDeletions(self, s: str) -> int:
    dp = 0
    b_count = 0
    for char in s:
        if char == 'b':
            # dp = dp (redundant)
            b_count += 1
        else:
            dp = min(dp + 1, b_count)  # This overwrites dp immediately
    return dp

Solution: If optimizing space, use a separate variable for the previous state:

def minimumDeletions(self, s: str) -> int:
    min_deletions = 0
    b_count = 0
    for char in s:
        if char == 'b':
            b_count += 1
        else:
            min_deletions = min(min_deletions + 1, b_count)
    return min_deletions