Minimum Deletions to Make String Balanced

Medium
1028.

Minimum Deletions to Make String Balanced

Minimum Deletions to Make String Balanced is a medium coding problem on strings, dynamic programming and stack, asked in Amazon, Google and Uber interviews.

s contains only 'a' and 'b'. It is balanced when there is no pair of indices i < j with s[i] = 'b' and s[j] = 'a' — in other words, every a comes before every b.

Return the minimum number of characters you must delete to make s balanced.

Example 1

Input
s = "aababbab"
Output
2
Explanation
Delete the two `a`s after the first `b`, leaving `aabbbb`.

Example 2

Input
s = "bbaaaaabb"
Output
2
Explanation
Delete the two leading `b`s.

Example 3

Input
s = "aaaa"
Output
0
Explanation
Already balanced.

Constraints

  • 1 <= s.length <= 10^5
  • s[i] is 'a' or 'b'.
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {string} s
 * @return {number}
 */
var minimumDeletions = function(s) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Minimum Deletions to Make String Balanced — Solution

Minimum Deletions to Make String Balanced solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript.

Minimum Deletions to Make String Balanced is a medium coding problem on strings, dynamic programming and stack, asked in Amazon, Google and Uber interviews.

Problem statement

s contains only 'a' and 'b'. It is balanced when there is no pair of indices i < j with s[i] = 'b' and s[j] = 'a' — in other words, every a comes before every b.

Return the minimum number of characters you must delete to make s balanced.

Example 1

Input: s = "aababbab"
Output: 2
Explanation: Delete the two `a`s after the first `b`, leaving `aabbbb`.

Example 2

Input: s = "bbaaaaabb"
Output: 2
Explanation: Delete the two leading `b`s.

Example 3

Input: s = "aaaa"
Output: 0
Explanation: Already balanced.

Constraints

  • 1 <= s.length <= 10^5
  • s[i] is 'a' or 'b'.

Hints for Minimum Deletions to Make String Balanced

  1. Hint 1

    The result is always some prefix of as followed by a suffix of bs — you are choosing where the boundary falls.

  2. Hint 2

    Sweep left to right keeping the number of bs seen so far and the best cost for the prefix processed.

  3. Hint 3

    At an a you either delete it (cost + 1) or delete every b before it.

How to solve Minimum Deletions to Make String Balanced

Sweep once, carrying two numbers: bCount, the number of bs seen, and res, the cheapest way to balance the prefix so far. A b is always free to keep. An a forces a choice — delete this a, or delete all the bs before it — and the cheaper of the two is optimal.

Approach

  1. Start bCount = 0 and res = 0.
  2. On a 'b', increment bCount.
  3. On an 'a', set res = min(res + 1, bCount).
  4. Return res.

Why it works

Taking min(res + 1, bCount) is the whole algorithm, and it is correct because the two branches are exhaustive: in any balanced result this a is either gone, or it survives — and if it survives, no b before it can. bCount is exactly the cost of the second branch, and it needs no res term because deleting every earlier b already balances the prefix. Trying every boundary position with prefix sums is the same answer in two passes.

Complexity

  • Time — O(n)
  • Space — O(1)

Pitfalls

  • res + 1 is not always the better branch — deleting the earlier bs can be cheaper.
  • The two branches must not be added; exactly one of them happens.
  • bCount keeps counting even after a branch chooses to "delete" those bs — it is a cost estimate, not a live state.

Reference solution

Python

def minimumDeletions(s: str) -> int:
    b_count = 0
    res = 0
    for c in s:
        if c == "b":
            b_count += 1
        else:
            res = min(res + 1, b_count)
    return res

Java

public static int minimumDeletions(String s) {
    int bCount = 0, res = 0;
    for (int i = 0; i < s.length(); i++) {
        if (s.charAt(i) == 'b') bCount++;
        else res = Math.min(res + 1, bCount);
    }
    return res;
}

C++

int minimumDeletions(string s) {
    int bCount = 0, res = 0;
    for (char c : s) {
        if (c == 'b') bCount++;
        else res = min(res + 1, bCount);
    }
    return res;
}

JavaScript

var minimumDeletions = function(s) {
    var bCount = 0, res = 0;
    for (var i = 0; i < s.length; i++) {
        if (s.charAt(i) === "b") bCount++;
        else res = Math.min(res + 1, bCount);
    }
    return res;
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 515 strings problems · the whole catalogue

Learn the technique: Strings · Dynamic Programming