100分做法

这里介绍两种做法，一种时间复杂度o(nlogn),一种时间复杂度o(n)

1.二分 时间复杂度o(nlogn),空间复杂度o(1)

对于子序列的长度，对于每个len的长度是否可行，不难发现这个问题是单调的，也就是len可行len-1一定可行，所以对于枚举长度直接二分即可，代码如下

int i,n;
class Solution {
public:
    /**
     * 
     * @param x string字符串 
     * @return int整型
     */
    bool check(int m,string x)
    {
        int sum[3]={0};
        for(i=0;i<n;i++)
        {
            if(sum[0]<m)
            {
                if(x[i]=='a')sum[0]++;
            }
            else if(sum[1]<m)
            {
                if(x[i]=='b')sum[1]++;
            }
            else if(sum[2]<m)
            {
                if(x[i]=='c')sum[2]++;
            }
        }
        if(sum[2]==m)return 1;
        return 0;
    }
    int Maximumlength(string x) {
        n=x.size();
        int l=1,r=n/3,mid,pos=0;
        while(l<=r)
        {
            mid=(l+r)/2;
            if(check(mid,x)){pos=mid;l=mid+1;}
            else r=mid-1;
        }
        return 3*pos;
    }
};

2.前缀和优化枚举，时间复杂度o(n),空间复杂度o(n)

我们可以记录b的前缀和，在分别记录a从前往后出现的顺序与c从后往前出现的顺序，然后判断两者中间b的个数时候足够即可，代码如下：

int i,n;
int sum[1000005];
vector < int > a , c;
class Solution {
public:
    /**
     * 
     * @param x string字符串 
     * @return int整型
     */
    int Maximumlength(string x) {
       n=x.size();
        for(i=0;i<n;i++)
        {
            if(i!=0)sum[i]=sum[i-1];
            if(x[i]== 'a' )a.push_back(i);
            else if(x[i] =='c')c.push_back(i);
            else if(x[i] =='b' )sum[i]++;
        }
        reverse(c.begin(),c.end());
        int pos=0;
        for(i=0;i<a.size()&&i<c.size();i++)
        {
            if(c[i]<a[i])break;
            if(sum[c[i]]-sum[a[i]]<i+1)break;
            pos++;
        }
        return 3*pos;
    }
};