//双指针
class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     * 
     * @param x string字符串 
     * @return int整型
     */
    // typedef pair<int,int> pii;
    int Maximumlength(string x) {
        // write code here
        string s;
        for(auto c : x)
            if(c=='a' || c=='b' || c=='c')
                s += c; //只需要abc字符
        int n = s.size();
        if(n < 3) return 0;
        vector<int> numa(n+1, 0), numb(n+1, 0), numc(n+1, 0);//前缀和个数
        for(int i = 1; i <= n; i++)
        {
            if(s[i-1] == 'a')
            {
                numa[i] = numa[i-1] + 1;
                numb[i] = numb[i-1];
                numc[i] = numc[i-1];
            }
            else if(s[i-1] == 'b')
            {
                numa[i] = numa[i-1];
                numb[i] = numb[i-1]+1;
                numc[i] = numc[i-1];
            }
            else
            {
                numa[i] = numa[i-1];
                numb[i] = numb[i-1];
                numc[i] = numc[i-1]+1;
            }
        }
        int ans = 0, a = 0, b= 0, c= 0;
        int i = 1, j = n;
        // 贪心，让 a c，交替变多
        while(i <= j)
        {
            int MIN = min(a,min(b,c));//数量最少的
            if(MIN == a)
            {
                a = numa[i++];
            }
            else if(MIN == c)
            {
                c = numc[n]-numc[--j];
            }
            else
                break;
            b = numb[j]-numb[i-1];
            ans = max(ans, 3*min(a,min(b,c)));
        }
        return ans;
    }
};

//二分查找
class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     * 
     * @param x string字符串 
     * @return int整型
     */
    // typedef pair<int,int> pii;
    int Maximumlength(string x) {
        // write code here
        string s;
        for(auto c : x)
            if(c=='a' || c=='b' || c=='c')
                s += c;
        int n = s.size();
        if(n < 3) return 0;
        int l = 0, r = n/3, mid, ans = 0;
        while(l <= r)
        {
            mid = (l+r)/2;
            if(ok(s, mid))
            {
                ans = mid*3;
                l = mid+1;
            }
            else
                r = mid-1;
        }
        return ans;
    }
    bool ok(string& s, int n)
    {
        int a = 0, b =0, c = 0;
        for(int i = 0; i < s.size(); ++i)
        {
            if(a < n)
            {
                if(s[i] == 'a')
                    a++;
            }
            else if(b < n)
            {
                if(s[i]== 'b')
                    b++;
            }
            else
            {
                if(s[i] == 'c')
                    c++;
            }
        }
        return c >= n;
    }
};