LeetCode 1653 | Medium | Minimum Deletions to Make String Balanced

LeetCode 1653. Minimum Deletions to Make String Balanced

Intuition

What is a balanced string? In this problem, for every $i < j$ there is no $s[i] = b$ and $s[j] = a$.

We can conclude: the balanced string must be in format: aaaaaabbbbb!

Here we have the idea: for each index, assuming all a on the left, and all b on the right.

Then let’s write the subproblem.

Subproblem

let $DP[i]$ be the minimum deletions of string $s[1…i]$, then ask what is $DP[n]$.

Recursion

for each index i, there is a one case, as you can simply remove the current element whether it’s a or b.

\[DP[i] = DP[i-1] + 1\]

As the target is, you’re deleting a on the right and bon the left.

You can also delete all the b on the left, as $DP[i]$ only consider the substring $s[1…i]$.

\[DP[i] = Count_b[i]\]

To sum up, we have

\[DP[i] = min(DP[i-1] + 1, Count_b[i])\]

Note: you don’t need to update $DP[i]$ when there’s $s[i] = b$ because b could be taken as end of string. Then you have:

\[DP[i] = DP[i-1]\]

Finally we have the recursion.

\[DP[i] =\left\{\begin{matrix} & min(DP[i-1] + 1 , Count_b[i]) & s[i] = 'a' \\ & DP[i] & s[i] = 'b' \end{matrix}\right.\]

Complexity

• Time complexity: $\Theta(n)$ since 1d loop

• Space complexity: $\Theta(1)$ since no array used here The code given is a space optimized version. $\Theta(n)$ if you allocate 1d array for DP as mentioned before.

Code

class Solution:
    def minimumDeletions(self, s: str) -> int:
        ans = 0
        bcnt = 0
        for c in s:
            if c == 'b':
                bcnt += 1
            else:
                ans = min(ans+1, bcnt)

        return ans