Leetcode 1756 Solution

This article provides solution to leetcode question 1756 (minimum-deletions-to-make-string-balanced)
Categories:
Tags:
Access this page by simply typing in "lcs 1756" in your browser address bar if you have bunnylol configured.

https://leetcode.com/problems/minimum-deletions-to-make-string-balanced

Solution

class Solution:
    def minimumDeletions(self, s: str) -> int:
        n = len(s)

        dp1 = [0] * n
        dp2 = [0] * n

        cnt = 0
        for i, ch in enumerate(s):
            if ch == 'b':
                cnt += 1
            dp1[i] = cnt

        cnt = 0
        for i, ch in enumerate(list(reversed(s))):
            if ch == 'a':
                cnt += 1
            dp2[n - 1 - i] = cnt

        ans = min(dp1[-1], dp2[0])
        for i in range(n - 1):
            ans = min(dp1[i] + dp2[i + 1], ans)
        return ans