Minimum Deletions to Make String Balanced — Medium Problem & Solution

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…

Difficulty: Medium
Topics: Strings, Dynamic Programming, Stack
Asked at: Amazon, Google, Uber
Time limit: 2 s
Memory limit: 256 MB
Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby

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'.

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

Start bCount = 0 and res = 0.
On a 'b', increment bCount.
On an 'a', set res = min(res + 1, bCount).
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

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#, C++, Go, Java, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 282 strings problems · the whole catalogue