CodeForces - 1291D Irreducible Anagrams （结论题）

???? ???? ????

同构：两字符串字符集相同，但排列不同
给你一个字符串，求是否存在字符与他同构且他们的严格前缀不同构。

有可能存在的只有以下几种情况，考虑前缀不同构的时候要考虑到只要前缀字符集不同即可，所以类似a—a，b—b的情况我们直接删去再考虑，灰线表示匹配情况，只要所有线都交叉即存在

还有一点就是种类数不满足差分性质，，但是字符数量满足，统计种类数的时候枚举字符，检查当前字符左右边界数量是否改变即可

string s;
int sum[26][MAXN];//
void init()
{
    int n=sz(s);
    for(int i=0;i<n;++i)
    {
        for(int j=0;j<26;++j)
        {
            if(i==0) sum[j][i]=(s[i]-'a'==j?1:0);
            else sum[j][i]=sum[j][i-1]+(s[i]-'a'==j?1:0);
        }
    }
}
int solve(int l,int r)
{
    if(l==r||s[l]!=s[r]) return 1;
    map<char,int>mp;
    int num=0;
    rep(i,26)
        if(sum[i][r]>sum[i][l-1]) ++num;
    return num>2;
}
signed main()
{
    cin>>s;
    init();
    int T;cin>>T;
    while(T--)
    {
        int l,r;cin>>l>>r;
        if(solve(l-1,r-1)) cout<<"Yes\n";
        else cout<<"No\n";
    }
    return 0;
}