Problem Statement in English

You’re given a string s consisting only of characters 'a' and 'b'. In one step, you can delete one character from s. Your task is to make s balanced, which means there are no indices i < j such that s[i] == 'b' and s[j] == 'a'.

Return the minimum number of steps required to make s balanced.

Approach

This is the exact same problem as the one we solved in Leetcode 926. Flip String to Monotone Increasing. You can check out the solution to that problem here.

We can use the exact same code, but instead of checking for ‘0’ and ‘1’, we check for ‘a’ and ‘b’.

And we’re done!

Solution in Python


class Solution:
    def minimumDeletions(self, s: str) -> int:
        N = len(s)
        ones = 0
        res = N

        for c in s:
            if c == "b":
                ones += 1
            else:
                res = min(ones, res + 1)

        return min(res, N - ones)

Complexity

  • Time: $O(n)$
    Since we’re iterating through the string once.

  • Space: $O(1)$
    Since we’re only using a constant amount of extra space.

And we are done.