题解:
尺取法,因为这个题目让你找包含26个字母且长度最小的连续区间,所以我们考虑双指针这种算法,从左边往右边移动,每次判断一下确定的区间是否符合标准
1.如果符合标准的话,那么我们让左指针往右边移动,同时对应的删除左指针移动走的拿个字符。
2.如果不符合标注,那么我们需要让区间继续扩大,也就是让右指针往右移动,同时添加上我们新纳入这个区间的字符。
那么我们该如何判断这个区间是否符合标准呢?我们可以用一个数组来记录相应字母的出现次数即可,每次遍历一下这个数组看看是否每个字符都至少出现过一次。
代码:
/*Keep on going Never give up*/
#pragma GCC optimize(3,"Ofast","inline")
#include <bits/stdc++.h>
const int maxn = 200;
const int MaxN = 0x3f3f3f3f;
const int MinN = 0xc0c0c00c;
typedef long long ll;
const int mod = 100000000;
using namespace std;
string s;
int visited[maxn];
int main(){
cin>>s;
memset(visited,0,sizeof(visited));
int l=0,r=0,ans=MaxN,len=s.size();
while (true){
bool flag=true;
for(int i=0;i<26;i++){
if(visited[i]==0){
flag=false;
break;
}
}
if(flag){
ans=min(ans,r-l+1);
l++;
visited[s[l-1]-'a']--;
} else{
r++;
if(r==len) break;
visited[s[r]-'a']++;
}
}
cout<<ans<<endl;
return 0;
}

京公网安备 11010502036488号