题意: 一个字符串 s s s只有1,2,3,求最小的子串三者都包含.
0 ≤ ∣ s ∣ ≤ 2 e 5 0\leq|s|\leq2e5 0≤∣s∣≤2e5
分析:
通过归纳,最终的答案形式值只能是 a b b b . . . b b b c abbb...bbbc abbb...bbbc这种形式.感性的想如果现在是 a b . . . b a ab...ba ab...ba,那我前面的a完全可以不要,b只要1个然后去找 c c c.
思路有了,写法就很多样
#include<bits/stdc++.h>
using namespace std;
using i64 = long long;
#define ios ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
string s;
void solve(){
cin>>s;
int n = s.size();
s = ' '+s;
vector<pair<int,int>> c;
for(int i = 1;i<=n;++i){
if(c.empty()||c.back().first!=s[i]-'0') c.push_back({s[i]-'0',1});
else c.back().second++;
}
int ans = 0x3f3f3f3f;
for(int i = 1;i<c.size()-1;++i){
if(c[i-1].first!=c[i+1].first){
ans = min(ans,c[i].second+2);
}
}
cout<<(ans==0x3f3f3f3f?0:ans)<<"\n";
}
signed main(){
ios;
int t;
cin>>t;
while(t--){
solve();
}
return 0;
}