Editorial

Solution walkthrough

Review the explanation, then compare the reference implementation.

Video explanation

Solution

Intuition

A balanced string places every a before every b. A newly encountered b causes no immediate conflict. For a new a, either delete it while preserving the best earlier solution, or keep it and delete every preceding b.

Approach

Track the count of b characters seen and the minimum deletions for the processed prefix. Increment the count on b. On a, update the answer to the smaller of previousAnswer + 1 and the total preceding b count. The latter option keeps all earlier a characters, so no earlier deletions must be added to it. Return the final prefix answer.

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

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

        return res

Complexity analysis

Let n = s.length. Time: O(n) for one left-to-right pass. Auxiliary space: O(1).