# 1653.使字符串平衡的最少删除次数 (Medium)

## 问题描述
[1653. 使字符串平衡的最少删除次数 (Medium)](https://leetcode.cn/problems/minimum-deletions-to-make-string-balanced/)

给你一个字符串 `s` ，它仅包含字符 `'a'` 和 `'b'`  。

你可以删除 `s` 中任意数目的字符，使得 `s` **平衡** 。当不存在下标对 `(i,j)` 满足 `i < j`
，且 `s[i] = 'b'` 的同时 `s[j]= 'a'` ，此时认为 `s` 是 **平衡** 的。

请你返回使 `s` **平衡** 的 **最少** 删除次数。

**示例 1：**

```
输入：s = "aababbab"
输出：2
解释：你可以选择以下任意一种方案：
下标从 0 开始，删除第 2 和第 6 个字符（"aababbab" -> "aaabbb"），
下标从 0 开始，删除第 3 和第 6 个字符（"aababbab" -> "aabbbb"）。

```

**示例 2：**

```
输入：s = "bbaaaaabb"
输出：2
解释：唯一的最优解是删除最前面两个字符。

```

**提示：**

- `1 <= s.length <= 10⁵`
- `s[i]` 要么是 `'a'` 要么是 `'b'` 。

## 解题思路
### 枚举分割线
分割线从0枚举到n(数字表示分割线左侧有多少个字符)，删除分割线左侧的'b'和右侧的'a'，删除次数的最小值即为答案。

### 动态规划
考虑`cnt[i]`为前`i`个字符中'b'的数量，`dp[i]`为使前`i`个字符平衡的最小操作数：
- 当`s[i - 1] == 'a'`时，`cnt[i] = cnt[i - 1]`，为了让前`i`个字符平衡，要么将这个'a'删掉，此时`dp[i] = dp[i - 1] + 1`，要么直接将前`i`个字符的的'b'全都删掉，此时`dp[i] = cnt[i]`；因此有`dp[i] = min(dp[i - 1] + 1, cnt[i])`；
- 当`s[i - 1] == 'b'`时，`cnt[i] = cnt[i - 1] + 1`，`dp[i] = dp[i - 1]`；

## 代码
### 枚举分割线
```cpp
class Solution {
  public:
    int minimumDeletions(string s) {
        // 两种选择，删掉不符合条件的'a'和删掉不符合条件的'b'
        // cnt[i][0]表示前i个字符中'a'的数目
        vector<vector<int>> cnt(s.size() + 1, vector<int>(2, 0));
        for (int i = 1; i <= s.size(); ++i) {
            if (s[i - 1] == 'a') {
                cnt[i][0] = cnt[i - 1][0] + 1;
                cnt[i][1] = cnt[i - 1][1];
            } else {
                cnt[i][0] = cnt[i - 1][0];
                cnt[i][1] = cnt[i - 1][1] + 1;
            }
        }
        int res = s.size();
        for (int i = 0; i <= s.size(); ++i) {
            res = std::min(res, i - cnt[i][0] + cnt[s.size()][0] - cnt[i][0]); // 枚举分割线，分割线左侧的'b'全删掉，分割线右侧的'a'全删掉
        }
        return res;
    }
};
```

### 动态规划
```cpp
class Solution {
public:
    int minimumDeletions(string s) {
        int n = s.size();
        vector<int> dp(n + 1, 0);
        vector<int> cnt(n + 1, 0); // 前n个字符中'b'的数目
        for (int i = 1; i <= n; ++i) {
            if (s[i - 1] == 'b') {
                cnt[i] = cnt[i - 1] + 1;
                dp[i] = dp[i - 1];
            } else {
                cnt[i] = cnt[i - 1];
                dp[i] = std::min(dp[i - 1] + 1, cnt[i]);    
            }
        }
        return dp[n];
    }
};
```