LC-1653 Medium LeetCode

1653. Minimum Deletions to Make String Balanced

Read the full problem statement on LeetCode.

Difficulty: medium Acceptance: 66% Topics: String, Dynamic Programming, Stack

Reading material

Strings 12 min 1-D Dynamic Programming 16 min Stacks & Queues 11 min

Reference solution (spoiler · python)

# Time:  O(n)
# Space: O(1)

class Solution(object):
    def minimumDeletions(self, s):
        """
        :type s: str
        :rtype: int
        """
        result = b_cnt = 0
        for c in s:
            if c == 'b':
                b_cnt += 1
            elif b_cnt:
                b_cnt -= 1
                result += 1
        return result

Solution from kamyu104/LeetCode-Solutions · MIT