: https://leetcode.com/problems/minimum-deletions-to-make-string-balanced
: ※ 引述《enmeitiryous (enmeitiryous)》之銘言：
: : 1653 minimun deletion make string balance
想說先把ab切出來
看起來比較清楚
要斷在哪就把後面的a跟前面的b砍了
不過邊分邊扣好像就好了
不用開n
有多少扣多少 不用的補回去
意思一樣
省流省空間
懶ㄉ改
class Solution {
public:
int minimumDeletions(string s) {
vector<int> a, b;
bool sw = true;
int cnt = 0;
for(char c: s){
if(sw){
if(c == 'a') cnt++;
else {
a.push_back(cnt);
cnt = 1;
sw = !sw;
}
}
else{
if(c == 'b') cnt++;
else{
b.push_back(cnt);
cnt = 1;
sw = !sw;
}
}
}
if(sw) a.push_back(cnt);
else b.push_back(cnt);
if(a.size() > b.size()) b.push_back(0);
int n = a.size();
int del = accumulate(a.begin(), a.end(), 0) - a[0];
int res = del;
for(int i = 1; i < n; i++){
del = del - a[i] + b[i-1];
res = min(res, del);
}
return res;
}
};