# Leetcode 1653. Minimum Deletions to Make String Balanced
###### tags: `leetcode` `殘酷daily` `string` `DP`

[題目連結](https://leetcode.com/problems/minimum-deletions-to-make-string-balanced/)

# Method
:::info
:bulb: **作法講解**:
Concept:
var "cur_a" means how many deleted character that
keep last character is a
var "cur_b" means how many deleted character that keep last character is b
initialize "cur_a" to 0, "cur_b" to 0

we scan string s from start to end (0 -> n - 1)
step 1: compute cur_b is minimum between cur_a and cur_b
if s[i] is 'a', than increase cur_b.

step 2: if s[i] is 'b', than increase cur_a.

finally, return minimum between cur_a and cur_b
:::

TC: O(N) SC: O(1)
:::spoiler 完整程式碼

class Solution {
public:
    int minimumDeletions(string s) {
        int n = s.size();
        int cur_a = 0; //how many deleted character when cur character is a
        int cur_b = 0; //how many deleted character when cur character is b

        for(int i = 0 ; i < n ; i++) {
            cur_b = min(cur_a, cur_b) + (s[i] == 'a');
            cur_a += (s[i] == 'b');
        }
        return min(cur_a, cur_b);
    }
};

:::