Nikita and string CodeForces - 877B

Nikita and string CodeForces - 877B

有一个全由a和b组成的字符串，可以切成三部分。满足如下规则：

• 第一部分只包含a或者是空串。
• 第二部分只包含b或者是空串。
• 第三部分只包含a或者是空串。

为了使原串符合条件，可以去掉原串中的一些字符，但不可以改变顺序。

Input

输入为一个只包含 a 和 b 的串，且长度不超过 5000。

Output

输出一个整数。整数为切完后三部分串长度的总和的最大值。
如样例1，abba 可以在不删除任何字符的情况下切成 a+bb+a，所以长度总和为 4。
如样例2，ba b可以在删除第一个字符的情况下切成 a+b+NULL，所以长度总和为 2。

Sample Input

abba
bab

Sample Output

4
2

分析

数据可以分为：空,a,b,ab,ba,aba - 五类，相互间存在依存关系，如：
a 一定是 a,ba,aba 的一部分，
b 一定是 b,ab,aba 的一部分，
ab,ba 一定是 aba 的一部分。

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N=1e6+10,INF=0x3f3f3f3f;

int main(){
// freopen("data.in", "r", stdin);
    string s;
    while(cin>>s){
        int a=0, b=0, ab=0, ba=0, aba=0;
        for(int i=0; i<s.size(); i++){
            if(s[i]=='a') a++,ba++,aba++;
            else b++, ab++;
            ab = max(ab, max(a, b));
            ba = max(ba, max(a, b));
            aba = max(aba, max(ab, ba));
        }
        cout<<aba<<endl;
    }
    return 0;
}