{x}
blog image

Minimum Deletions to Make String Balanced

You are given a string s consisting only of characters 'a' and 'b'​​​​.

You can delete any number of characters in s to make s balanced. s is balanced if there is no pair of indices (i,j) such that i < j and s[i] = 'b' and s[j]= 'a'.

Return the minimum number of deletions needed to make s balanced.

 

Example 1:

Input: s = "aababbab"
Output: 2
Explanation: 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
Explanation: The only solution is to delete the first two characters.

 

Constraints:

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

Minimum Deletions to Make String Balanced

This problem asks for the minimum number of deletions needed to make a string consisting of 'a' and 'b' characters balanced. A balanced string has no 'b' appearing before an 'a'. Several approaches can solve this efficiently.

Approach 1: Dynamic Programming

This approach uses dynamic programming to build a solution iteratively. We define f[i] as the minimum deletions needed to balance the first i characters of the string.

State Transition:

  • If the current character is 'b', we don't need to delete it (it doesn't violate the balance condition at this point), so f[i] = f[i-1]. We increment a counter b to track the number of 'b's encountered so far.
  • If the current character is 'a', we have two choices:
    • Delete the 'a': f[i] = f[i-1] + 1
    • Delete preceding 'b's: f[i] = b (we delete all preceding 'b's to make the string balanced)

We choose the minimum of these two options.

Time Complexity: O(n), where n is the length of the string. We iterate through the string once. Space Complexity: O(n) in the basic DP implementation. However, it can be optimized to O(1) as shown in the code examples below.

class Solution:
    def minimumDeletions(self, s: str) -> int:
        n = len(s)
        ans = 0  # Optimized to O(1) space
        b = 0
        for i in range(n):
            if s[i] == 'b':
                b += 1
            else:
                ans = min(ans + 1, b)
        return ans

The optimized Python code above eliminates the need for a DP array by directly maintaining the minimum deletions (ans) and the count of 'b's (b). Other languages demonstrate similar optimizations.

Approach 2: Two-Pointer/Greedy Approach

This is a more efficient and intuitive approach. We iterate through the string, maintaining two counters:

  • lb: Counts the number of 'b's encountered so far.
  • ra: Counts the number of 'a's remaining in the suffix of the string (initially, the total number of 'a's).

For each character:

  • If it's 'a', we decrement ra.
  • If it's 'b', we increment lb.
  • We update the minimum deletions (ans) as min(ans, lb + ra).

Time Complexity: O(n) Space Complexity: O(1)

class Solution:
    def minimumDeletions(self, s: str) -> int:
        lb, ra = 0, s.count('a')
        ans = len(s) # Initialize with maximum possible deletions
        for c in s:
            ra -= c == 'a'
            ans = min(ans, lb + ra)
            lb += c == 'b'
        return ans

This approach directly calculates the minimum deletions without explicitly building a DP table.

Approach 3: Stack (Less Efficient)

A stack-based approach is possible but less efficient than the previous two. The idea is to push characters onto a stack. When you encounter a 'b' followed by an 'a', you pop the 'b' and increment the deletion count. However, this approach requires O(n) space for the stack, making it less optimal than the O(1) space solutions above.

Choose either Approach 1 (optimized) or Approach 2 for optimal performance. Approach 2 is generally preferred for its clarity and efficiency. Avoid Approach 3 due to higher space complexity.