1653. Minimum Deletions to Make String Balanced

Time: O(n)

Space: O(1)

Intuition

Minimum characters to delete to make s consist of some a's followed by some b's. Scan left to right: delete b's seen so far or a's ahead.

Algorithm

1Count total b's. Scan: at each position, if char is a: b_ahead decreases. If char is b: a_before increases.
2Answer = min(a_before + b_ahead_after) over all split positions.

Common Pitfalls

•Answer = min over all split positions of: b's to the left (delete) + a's to the right (delete).

1653.cs

// Approach: DP — dp = min deletions so far; increment on 'a' after 'b' (delete this 'a' or all preceding 'b's).
// Time: O(n) Space: O(1)

public class Solution
{
    public int MinimumDeletions(string s)
    {
        int dp = 0;
        int cntB = 0;

        foreach (char ch in s)
        {
            if (ch == 'a')
                dp = Math.Min(dp + 1, cntB);
            else
                cntB++;
        }

        return dp;
    }
}

Was this solution helpful?