Problem

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.

Examples

Example 1:

Input: s = "aababbab"
Output: 2
Explanation: You can either:
Delete the characters at 0-indexed positions 2 and 6 ("aa{b}abb{a}b" -> "aaabbb"), or
Delete the characters at 0-i ndexed positions 3 and 6 ("aab{a}bb{a}b" -> "aabbbb").

Example 2:

Input: s = "bbaaaaabb"
Output: 2
Explanation: The only solution is to delete the first two characters.

Solution

Here is the video explanation with multiple solutions:

Method 1 - Handling deletion of a or not

For string be balanced, we need as on left and bs on right. In simpler terms, all ‘a’s should come before any ‘b’s, and we can do that by deleting minimum number of characters.

To make s balanced, ideally, there should be no ‘b’ before an ‘a’. This means that all ‘b’s should be located to the right of all ‘a’s.

Lets track 2 variables:

  1. bCount: Number of ‘b’s encountered ⇨ This count helps us understand how many ‘b’s are there so far that might need to be considered for deletion if ‘a’s follow.
  2. delCount: Track the minimum deletions needed to balance the string

Now, our algorithm will be:

  • We can iterate from left to right in string. Now, we can either encounter a or b.
  • If we encounter a,
    • we have 2 choices:
      1. Either we delete this a, which will increase delCount by 1, OR
      2. Or we delete all previous b’s we counted so far as bCount, to balance the string from the start
    • We choose the minimum of these 2 options: delCount = min(delCount, bCount), to ensure least number of deletions
  • If we encounter b, we just increment bCount

Code

Java
class Solution {

	public int minimumDeletions(String s) {
		int bCount = 0;
		int delCount = 0;

		for (char c: s.toCharArray()) {
			if (c == 'b') {
				bCount++;
			} else {
				// In this case, c is 'a'
				delCount = Math.min(delCount + 1, bCount);
			}
		}

		return delCount;
	}
}

Complexity

  • ⏰ Time complexity: O(n), where n is length of string
  • 🧺 Space complexity: O(1)

Dry Run

Lets take s = "aababbab", and initialize bCount = 0, delCount = 0 Now, the traversal is:

  1. ‘a’: Compare delCount + 1 (1) and bCount (0) -> delCount = 0
  2. ‘a’: Compare delCount + 1 (1) and bCount (0) -> delCount = 0
  3. ‘b’: Increment bCount -> bCount = 1
  4. ‘a’: Compare delCount + 1 (1) and bCount (1) -> delCount = 1
  5. ‘b’: Increment bCount -> bCount = 2
  6. ‘b’: Increment bCount -> bCount = 3
  7. ‘a’: Compare delCount + 1 (2) and bCount (3) -> delCount = 2
  8. ‘b’: Increment bCount -> bCount = 4

Method 2 - Using Stack

This solution is similar to Valid Parentheses Problem. The stack will help us keep track of the characters as we iterate through the string, allowing us to simulate the deletions required to maintain the balance. At any point, we shouldn’t allow b before a, similar to we don’t allow ) before (. Here are the steps we can take:

  1. Traverse through the string while using a stack to maintain the characters in a way that ensures balance.
  2. For each character:
    • If it’s a ‘b’, push it onto the stack.
    • If it’s an ‘a’ and there are ‘b’s on the stack that occur before it (making the string unbalanced), then pop the ‘b’s from the stack (these ‘b’s are conceptually “deleted”).
  3. The number of deletions required will be the number of elements that have been removed from the stack plus any remaining ‘a’s that couldn’t be balanced within the stack.

Code

Java
public class Solution {

	public static int minimumDeletions(String s) {
		Stack<Character> stack = new Stack<>();
		int deletions = 0;

		for (char c: s.toCharArray()) {
			if (c == 'b') {
				stack.push(c);
			} else if (c == 'a') {
				// If there are 'b's in the stack, which make the string unbalanced
				if (!stack.isEmpty() && stack.peek() == 'b') {
					// Pop the 'b' to resolve the imbalance
					stack.pop();
					deletions++;
				}
			}
		}

		return deletions;
	}
}

Complexity

  • ⏰ Time complexity: O(n)
  • 🧺 Space complexity: O(n) for using the stack

Method 3 - Count b’s on left and a’s on right

We can use two arrays to solve this problem by keeping track of the number of ‘b’s to the left of each index and the number of ‘a’s to the right of each index. This will allow us to determine the minimum deletions required at each position to make the string balanced.

Here are the steps:

  1. Left Pass: Use an array to count the cumulative number of ‘b’s to the left of each index.
  2. Right Pass: Use another array to count the cumulative number of ‘a’s to the right of each index.
  3. Combine Information: Use the two arrays to determine the minimum deletions required at each index to make the string balanced.

Code

Java
public class Solution {

	public static int minDeletionsToMakeBalanced(String s) {
		int n = s.length();

		// Array to store the number of 'b's to the left of each index
		int[] countBLeft = new int[n + 1];

		// Array to store the number of 'a's to the right of each index
		int[] countARight = new int[n + 1];

		// Populate countBLeft
		for (int i = 0; i < n; i++) {
			countBLeft[i + 1] = countBLeft[i] + (s.charAt(i) == 'b' ? 1 : 0);
		}

		// Populate countARight
		for (int i = n - 1; i >= 0; i--) {
			countARight[i] = countARight[i + 1] + (s.charAt(i) == 'a' ? 1 : 0);
		}

		// Calculate the minimum deletions
		int minDeletions = Integer.MAX_VALUE;

		for (int i = 0; i <= n; i++) {
			minDeletions = Math.min(minDeletions, countBLeft[i] + countARight[i]);
		}

		return minDeletions;
	}
}

Complexity

  • ⏰ Time complexity: O(n)
  • 🧺 Space complexity: O(n) for using aux array.