题目大意

给定一个只包含字符 a 和 b 的字符串，通过删除字符（可以不删除）将其转化为满足以下条件的最长字符串：

1. 字符串可以分为三段。
2. 第一段和第三段仅包含 a。
3. 第二段仅包含 b。
4. 每一段都可以为空。

解决思路

可以使用动态规划解决，$dp_{i,j}$ 表示前 $i$ 个字符，第 $j$ 段时，最长美丽字符串的长度，其中 $j\in{0,1,2}$。

可以考虑逐个考虑字符串 $s$ 的每一位：

如果 $s_i$ 是 a，那么：

• $dp[i][0]=dp[i-1][0]+1$，即第一段延长；
• $dp[i][1]=dp[i-1][1]$，即第二段不变；
• $dp[i][2]=\max(dp[i-1][1],dp[i-1][2])+1$，即第三段开始或延长。

如果 $s_i$ 是 b，那么：

• $dp[i][0]=dp[i-1][0]$，即第一段不变；
• $dp[i][1]=\max(dp[i-1][0],dp[i-1][1])+1$，即第二段开始或延长；
• $dp[i][2]=dp[i-1][2]$，即第三段不变。

则最终答案是 $\max(dp[n][0],\max(dp[n][1],dp[n][2]))$，其中，$n$ 为字符串 $s$ 的长度。

代码

#include<bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>
#define int long long
#define tem template
#define sizet size_t
#define il inline
#define uni union
#define endl "\n"
const int INF=0xfffffff;
using namespace std;
using namespace __gnu_pbds;
using namespace __gnu_cxx;
int dp[5005][3];
signed main()
{
    char a;
    a=getchar();
    dp[0][0]=dp[0][2]=(a=='a')?1:0;//初始化
    dp[0][1]=1-dp[0][0];
    string s;
    cin>>s;
    for(int i=0;i<s.size();i++)
    {
        if(s[i]=='a')//状态转移
        {
            dp[i+1][0]=dp[i][0]+1;
            dp[i+1][1]=dp[i][1];
            dp[i+1][2]=max(dp[i][1],dp[i][2])+1;
        }
        else
        {
            dp[i+1][0]=dp[i][0];
            dp[i+1][1]=max(dp[i][0],dp[i][1])+1;
            dp[i+1][2]=dp[i][2];
        }
    }
    cout<<max(dp[s.size()][0],max(dp[s.size()][1],dp[s.size()][2]))<<endl;
    return 0;
}

时间复杂度

$O(|s|)$，其中 $|s|$ 是字符串 $s$ 的长度。

空间复杂度

$O(|s|)$。