【问题描述】
给定一个由字符'a'和字符'b'组成的字符串，可以删除若干字符，使得剩下来的字符串满足前后段为a，中间段为b（aaa....aaabbbb.....bbbbaaa.....aaa）,区段可以没有字符（ba,ab,b,aa都是合法的），求最长剩下字符串的长度。
【输入形式】
输入为一行一个长度不超过5000的非空字符串，字符串仅由字符'a'和字符'b'组成。
【输出形式】
输出为一个整数，表示符合要求的最长剩下字符串长度
【样例输入1】
abba
【样例输出1】
4
【样例输入2】
bab
【样例输出2】
2
【思路分析】
前/后缀dp+分界点枚举。很显然，对于输入的字符串，我们需要贪心地取所有部分并判断是否满足题设条件。题设条件需要满足原字符串存在两个分界点，使前分界点前全为a，后分界点全为a，中间部分全为b。利用双循环有序遍历每个分界点排列情况，中间部分也可用前缀优化。
本题的时间复杂度为，其中n为字符串长度。
#include <iostream>
#include <vector>
#include <unordered_map>
#include <map>
#include <cmath>
#include <algorithm>
#include <climits>
#include <stack>
#include <cstring>
#include <iomanip>
#include <set>
#include <queue>#define i64 long longusing namespace std;void solve() {string s;cin>>s;i64 pre[s.size()+1],suf[s.size()+1],ans = 0,cnta = 0;memset(pre,0, sizeof pre);memset(suf,0, sizeof suf);for (int i = 1; i <= s.size(); ++i) {if (s[i-1] == 'a') pre[i]+=pre[i-1]+1;else pre[i] = pre[i-1];}for (int i = s.size() - 1; i >= 0; --i) {if (s[i] == 'a') suf[i]+=suf[i+1]+1;else suf[i] = suf[i+1];}for (int l = 0; l <= s.size(); ++l) {i64 mid = 0;for (int r = l+1; r <= s.size(); ++r) {if (s[r-1]=='b') mid++;ans = max(ans, pre[l] + suf[r]+mid);}}for (const auto &item: s) {if (item == 'a') cnta++;}ans = max(ans,cnta);cout<<ans;
}int main() {ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);int t = 1;
// cin >> t;while (t--) {solve();}return 0;
}
