BinarySearch 0310 As Before Bs

Problem statement

https://binarysearch.com/problems/As-Before-Bs/

Solution

Equal to Leetcode 1653. Minimum Deletions to Make String Balanced. The idea is to use dp with states end_a and end_b, where end_a is the minimum number of deletions such that we have last symbol a and similar for b.

Complexity

It is O(n) for time and O(1) for space.

Code

class Solution:
    def solve(self, s):
        end_a, end_b = 0,0 
        for val in s:
            if val == "A":
                end_b += 1
            else:
                end_a, end_b = end_a + 1, min(end_a, end_b)
        return min(end_a, end_b)