1653. Minimum Deletions to Make String Balanced

Medium

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 <= 10⁵
s[i] is a or b.

Hint:

You need to find for every index the number of Bs before it and the number of A's after it
You can speed up the finding of A's and B's in suffix and prefix using preprocessing

Solution:

To solve this problem, we can follow these steps:

Preprocess the counts of 'b's up to each index: This helps in knowing how many 'b's are present before any given index.
Preprocess the counts of 'a's from each index: This helps in knowing how many 'a's are present after any given index.
Calculate the minimum deletions needed: For each index, you can calculate the deletions needed by considering deleting all 'b's before it and all 'a's after it.

Let's implement this solution in PHP: 1653. Minimum Deletions to Make String Balanced

<?php
// Test cases
echo minimumDeletions("aababbab") . "\n"; // Output: 2
echo minimumDeletions("bbaaaaabb") . "\n"; // Output: 2
?>

Explanation:

Prefix Array for 'b's: This array keeps track of the cumulative count of 'b's up to each index. For example, if the string is "aababbab", the prefix array for 'b's will be [0, 0, 1, 2, 2, 3, 3, 4].
Suffix Array for 'a's: This array keeps track of the cumulative count of 'a's from each index to the end. For the same string, the suffix array for 'a's will be [4, 3, 3, 2, 2, 1, 1, 0].
Calculating Minimum Deletions: For each index i, the total deletions needed to make the string balanced if we split at i can be calculated as the sum of 'b's before i and 'a's after i. The minimum of these values across all indices gives the result.

This approach ensures that the solution is efficient with a time complexity of (O(n)), which is suitable given the constraints.

Contact Links

If you found this series helpful, please consider giving the repository a star on GitHub or sharing the post on your favorite social networks 😍. Your support would mean a lot to me!

If you want more helpful content like this, feel free to follow me:

LinkedIn
GitHub