---
# System prepended metadata

title: Leetcode 1653. Minimum Deletions to Make String Balanced
tags: [DP, leetcode, 殘酷daily, string]

---

# 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 完整程式碼
```cpp=
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);
    }
};
```
:::


