题解：CF2145C Monocarp's String

· · 题解

考虑赋权，把所有的 a 设成 1，把所有的 b 设成 -1，题意就转化成需要删除一段区间 [l,r]，使得 [1,l-1] 的前缀和与 [r+1,n] 的后缀和之和为 0。

考虑把每一个点的后缀和算出来，然后开 n 个桶，id_i 表示后缀和为 i 的所有下标。这个可以 vector 或者 set 之类的维护。

然后从前往后枚举 l，顺便计算前缀和 pre，然后再对应的桶 id_{-pre} 查询大于等于 l 的最小值就是确定这个左端点的最优的 [l,r]。

然后把所有的 l，算出最优的 r，计算 r-l-1（注意这个时候 l 和 r 是不能删除的）的最小值就是答案。

:::success[通过代码]

#include<bits/stdc++.h>
#define ll long long
using namespace std;
constexpr ll maxn=2e5+5;
ll T,n,arr[maxn];
char ch[maxn];
set<ll> id[maxn<<2]; 
void solve(){
    cin>>n>>(ch+1);
    for(int i=1;i<=n;i++){
        if(ch[i]=='a')arr[i]=1;
        if(ch[i]=='b')arr[i]=-1;
    }   
    for(int i=-n;i<=n;i++){
        id[i+maxn].clear();
    }
    ll suf=0,ans=n,pre=0;
    id[0+maxn].insert(n+1);
    for(int i=n;i>=1;i--){
        suf+=arr[i];
        id[suf+maxn].insert(i);
    }
    if(suf==0){
        cout<<0<<"\n";
        return;
    }
    for(int i=0;i<=n;i++){
        pre+=arr[i];
        auto nxt=id[-pre+maxn].upper_bound(i);
        if(nxt==id[-pre+maxn].end())continue;
        ll pp=*nxt;
        ans=min(ans,pp-i-1);
    }
    if(ans==n){
        cout<<-1<<"\n";
        return;
    }
    cout<<ans<<"\n";
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin>>T;
    while(T--){
        solve();
    }
    return 0;
}

:::