1653. 使字符串平衡的最少删除次数（在哪里切一刀？） · znzryb
## 题目大意
**题目：1653. 使字符串平衡的最少删除次数**
**题面总结：**
给定一个仅包含 'a' 和 'b' 的字符串 $s$，要求删除最少数量的字符，使得剩余字符串达到“平衡”状态。
**平衡状态定义：**
不存在下标对 $(i, j)$ 使得 $i < j$ 且 $s[i] = 'b'$ 同时 $s[j] = 'a'$。换言之，平衡后的字符串中，所有的 'a' 必须出现在所有的 'b' 之前（如 `"aaa"`, `"bbb"`, `"aaabbb"` 均为平衡状态）。
**样例解释：**
- **示例 1：** `s = "aababbab"`
- 方案 A：删除下标 2 和 6 的字符，得到 `"aaabbb"`，删除次数 2。
- 方案 B：删除下标 3 和 6 的字符，得到 `"aabbbb"`，删除次数 2。
- **结论：** 最少删除次数为 2。
- **示例 2：** `s = "bbaaaaabb"`
- 方案：删除前两个 'b'，得到 `"aaaaabb"`。
- **结论：** 最少删除次数为 2。
**数据范围：**
- $1 \le s.length \le 10^5$
- $s[i]$ 仅为 'a' 或 'b'。
说白了就是**形如AABBB，AABB**，就是**A在前B在后这样子**的呃样子**才是平衡状态**。
问，**把原字符串变成平衡状态**，需要**最少删除**多少个字符？
## 思路讲解
思路就是切一刀。如何快速计算在这里切一刀，可以得到的收益是多少呢？可以利用前缀，后缀。
```cpp
class Solution {
public:
int minimumDeletions(string s) {
s.insert(s.begin(),'#');
ll N=s.size();
vector<ll> pre_a(N+2),suf_a(N+2),pre_b(N+2),suf_b(N+2);
for(int i=1;i<=N;++i){
pre_a[i]=pre_a[i-1]+(s[i]=='a');
pre_b[i]=pre_b[i-1]+(s[i]=='b');
}
for(int i=N;i>=1;--i){
suf_a[i]=suf_a[i+1]+(s[i]=='a');
suf_b[i]=suf_b[i+1]+(s[i]=='b');
}
ll ans=INF;
for(int i=1;i<=N+1;++i){
ans=min(ans,pre_b[i-1]+suf_a[i]);
}
return ans;
}
};
```
[https://leetcode.cn/problems/minimum-deletions-to-make-string-balanced/submissions/697116504](https://leetcode.cn/problems/minimum-deletions-to-make-string-balanced/submissions/697116504)
也可以用DP做DP状态设计，就是第 I 位以A结尾还是以B结尾啊，然后进行这个DP状态转移即可。
下面的代码当中，这个零代表以A结尾，一代表以B结尾。
```go
func minimumDeletions(s string) int {
// b := []byte(s)
n := len(s)
dp := make([][]int, 2)
for i := range dp {
dp[i] = make([]int, n)
}
if s[0] == 'a' {
dp[0][0] = 0
dp[1][0] = 1
} else {
dp[0][0] = 1
dp[1][0] = 0
}
for i:=1;i<n;i++ {
if s[i] == 'a' {
dp[0][i] = dp[0][i-1]
dp[1][i] = dp[1][i-1] + 1
} else {
dp[0][i] = dp[0][i-1] + 1
dp[1][i] = min( dp[1][i-1], dp[0][i-1])
}
}
return min( dp[0][n-1], dp[1][n-1] )
}
```
## AC代码
[https://leetcode.cn/problems/minimum-deletions-to-make-string-balanced/submissions/697109197](https://leetcode.cn/problems/minimum-deletions-to-make-string-balanced/submissions/697109197)
::: 源代码
```cpp
#define all(vec) vec.begin(),vec.end()
#define PB push_back
#define PF push_front
#define EB emplace_back
#define EF emplace_front
#define EM emplace
#define FI first
#define SE second
#define pct __builtin_popcountll
#define ctz __builtin_ctzll
#define lson(o) (o<<1)
#define rson(o) (o<<1|1)
#define SZ(a) ((long long) a.size())
#define FOR(i, a, b) for (int i = (a); i <= (b); ++i)
#define ROF(i, a, b) for (int i = (a); i >= (b); --i)
#define debug(var) cerr << #var <<":"<<var<<"\n";
#define cend cerr<<"\n-----------\n"
#define fsp(x) fixed<<setprecision(x)
#define minn(vec) *min_element(vec.begin(),vec.end())
#define maxx(vec) *max_element(vec.begin(),vec.end())
#define yyy cout<<"YES\n"
#define nnn cout<<"NO\n"
using namespace std;
using ll = long long;using ull = unsigned long long;
using DB=double;using LD=long double;
// using i128 = __int128;
using CD=complex<double>;
static constexpr ll MAXN=(ll)1e6+10,INF=(1ll<<61)-1;
static constexpr ll mod=(ll)1e9+7; // 998244353;
static constexpr double eps=1e-8;const double pi=acos(-1.0);
// -------------------------------------------
class Solution {
public:
int minimumDeletions(string s) {
s.insert(s.begin(),'#');
ll N=s.size();
vector<ll> pre_a(N+2),suf_a(N+2),pre_b(N+2),suf_b(N+2);
for(int i=1;i<=N;++i){
pre_a[i]=pre_a[i-1]+(s[i]=='a');
pre_b[i]=pre_b[i-1]+(s[i]=='b');
}
for(int i=N;i>=1;--i){
suf_a[i]=suf_a[i+1]+(s[i]=='a');
suf_b[i]=suf_b[i+1]+(s[i]=='b');
}
ll ans=INF;
for(int i=1;i<=N+1;++i){
ans=min(ans,pre_b[i-1]+suf_a[i]);
}
return ans;
}
};
// string sorted_s=s;
// sort(all(sorted_s));
// ll ans=INF;
// do{
// ll del_a=0;
// ll cnt_b=0;
// for(int i=0;i<s.size();++i){
// if(s[i]=='a'){
// if(cnt_b>0){
// del_a++;
// }
// }else{
// ++cnt_b;
// }
// }
// ans=del_a;
// }while(false);
// do{
// ll del_b=0;
// ll cnt_b=0;
// for(int i=0;i<s.size();++i){
// if(s[i]=='a'){
// del_b+=cnt_b;
// cnt_b=0;
// }else{
// ++cnt_b;
// }
// }
// ans=min(ans,del_b);
// }while(false);
// return ans;
```
:::
[https://leetcode.cn/problems/minimum-deletions-to-make-string-balanced/submissions/697116504](https://leetcode.cn/problems/minimum-deletions-to-make-string-balanced/submissions/697116504)
::: 父亲的DP做法代码，go语言
```go
func minimumDeletions(s string) int {
// b := []byte(s)
n := len(s)
dp := make([][]int, 2)
for i := range dp {
dp[i] = make([]int, n)
}
if s[0] == 'a' {
dp[0][0] = 0
dp[1][0] = 1
} else {
dp[0][0] = 1
dp[1][0] = 0
}
for i:=1;i<n;i++ {
if s[i] == 'a' {
dp[0][i] = dp[0][i-1]
dp[1][i] = dp[1][i-1] + 1
} else {
dp[0][i] = dp[0][i-1] + 1
dp[1][i] = min( dp[1][i-1], dp[0][i-1])
}
}
return min( dp[0][n-1], dp[1][n-1] )
}
```
:::
## 心路历程（WA，TLE，MLE……）