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.

Examples:

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").

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

Approach-1: Cancel pairs Approach
Whenever encounter a pair of “ba”, cancel both of them and count the number of cancellations.

Why this works?

Whether delete a or b depending on the the character right after the last cancellation is a or b; If a, we have to delete b’s in all cancellations, otherwise delete either a’s or b’s. Therefore, we are sure there is no ba in the string.

For this approach, it seems to be that it is more of finding the number of deletions rather than the minimum number of deletions. is there a proof that using a stack and cancelling bad pairs would lead us to the minimum deletions rather than just finding the number of deletions?

So, All indices of character(s) inside stack are less than that of those outside. Therefore, whenever we find a ‘b’ inside and a ‘a‘ outside of the stack, we have to delete 1 (either ‘a’ or ‘b’) to make the string balanced. In short, if there are total n bad pairs, then there must be n ‘b’‘s in front of n ‘a’‘s, and the n is the minimum deletions.

import java.io.*;
import java.util.*;

public class Sol {
    public int countAdjacentBaPairs(String s) {
        int cnt = 0;
        Deque<Character> stk = new ArrayDeque<>();
        for (char c : s.toCharArray()) {
            if (!stk.isEmpty() && stk.peek() == 'b' && c == 'a') {
                stk.pop();
                ++cnt;
            } else {
                stk.push(c);
            }
        }
        return cnt;
    }

    public static void main(String[] args) {
        Sol s = new Sol();
        String str = "aababbab";
        int res = s.countAdjacentBaPairs(str);
        System.out.println(res);
    }
}

Output:

Approach-2: Two passes with space O(1)

Count the occurrences of ‘a’ on the right and ‘b’ on the left for each index, find the mininum;
The minimum out of total ‘a’, total ‘b’ and the result in step 1 is the solution.

import java.io.*;
import java.util.*;

public class Sol {
    public int minimumDeletions(String s) {
        int a = s.chars().map(i -> i == 'a' ? 1 : 0).sum(); // Count 'a's
        int cnt = a, b = 0;
        for (int i = 0; i < s.length(); ++i) {
            if (s.charAt(i) == 'b') {
                cnt = Math.min(cnt, a + b++); // Track minimum deletions
            } else {
                --a; // Decrease 'a' count
            }
        }
        return Math.min(cnt, b); // Return the minimum deletions
    } 

    public static void main(String[] args) {
        Sol s = new Sol();
        String str = "aababbab";
        int res = s.minimumDeletions(str);
        System.out.println(res);
    }
}

Output:

Time complexity: O(n)
Space complexity: O(1)
where, n = s.length().