题目大意
题目：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。
数据范围：
说白了就是形如AABBB，AABB，就是A在前B在后这样子的呃样子才是平衡状态。
问，把原字符串变成平衡状态，需要最少删除多少个字符？
思路讲解
思路就是切一刀。如何快速计算在这里切一刀，可以得到的收益是多少呢？可以利用前缀，后缀。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
| 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
也可以用DP做DP状态设计，就是第 I 位以A结尾还是以B结尾啊，然后进行这个DP状态转移即可。
下面的代码当中，这个零代表以A结尾，一代表以B结尾。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
| func minimumDeletions(s string) int {
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
源代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
| #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 CD=complex<double>;
static constexpr ll MAXN=(ll)1e6+10,INF=(1ll<<61)-1;
static constexpr ll mod=(ll)1e9+7;
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;
}
};
|
https://leetcode.cn/problems/minimum-deletions-to-make-string-balanced/submissions/697116504
父亲的DP做法代码，go语言
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
| func minimumDeletions(s string) int {
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……）