题解 | #成双成对#

方法1：直接暴力O(n^2),正向枚举所有可能的子串,不过没给数据范围一般是不太可的

#include<bits/stdc++.h>
using namespace std;
int main(){
    string s;cin>>s;
    int n = s.size();
    int ans=0;
    for(int i=0;i<n;i++){//以i开头的子串
        int a=0,b=0,c=0,x=0,y=0,z=0;
        if(s[i]=='a')    a++;
        if(s[i]=='b')    b++;
        if(s[i]=='c')    c++;
        if(s[i]=='x')    x++;
        if(s[i]=='y')    y++;
        if(s[i]=='z')    z++;
        for(int j=i+1;j<n;j++){
            if(s[j]=='a')    a++;
            if(s[j]=='b')    b++;
            if(s[j]=='c')    c++;
            if(s[j]=='x')    x++;
            if(s[j]=='y')    y++;
            if(s[j]=='z')    z++;
            if(a%2==0 && b%2==0 && c%2==0 && x%2==0 && y%2==0 && z%2==0)    ans=max(ans,j-i+1);
        }
    }
    cout<<ans<<endl;
    return 0;
}

方法2：状态压缩+哈希表O(n),用二进制串存储abcxyz各个字符出现的状态,记录下该状态第一次出现的位置,当再次出现该状态时,两者之间的状态差一定是000000,即他们之间的字符串一定符合条件

#include<bits/stdc++.h>
using namespace std;
int main(){
    string s;cin>>s;
    int n = s.size();
    unordered_map<int,int> hash;
    hash[0]=-1;//全都为偶数的状态得从下标-1开始
    int ans=0,state=0;
    for(int i=0;i<n;i++){
        if(s[i]=='a')    state^=0x000001;//C++没有二进制表示法,便于观察直接上十六进制了反正没越界
        if(s[i]=='b')    state^=0x000010;
        if(s[i]=='c')    state^=0x000100;
        if(s[i]=='x')    state^=0x001000;
        if(s[i]=='y')    state^=0x010000;
        if(s[i]=='z')    state^=0x100000;
        if(hash.count(state))    ans=max(ans,i-hash[state]);//两者之间的坐标
        else    hash[state]=i;//记下下标
    }
    cout<<ans<<endl;
    return 0;
}

吐槽一下，题目中所说的最长字符串有点模糊，直接叫子串会清晰一些，一开始还以为字符串一定要从下标0开始。