Codeforces 701C They Are Everywhere（Two pointers+STL）
【题目链接】 http://codeforces.com/problemset/problem/701/C
【题目大意】
给出 一个字符串，里面包含一定种类的字符，求出一个最短的子串，使得其包含该字符串中的所有种类的字符
【题解】
利用双指针，每次找到包含所有字符的串，用这个串的长度去更新答案，在判断该字符在选定串中出现次数的时候可以调用map，而统计不同种类字符个数则可以利用STL中的set进行统计。
【代码】
#include<set>
#include<map>
#include<cstdio>
#include<cstring>
using namespace std;
int n,ans,L=0,R=0,cnt=0;
set<int> s;
map<int,int> f;
char a[100005];
int main(){
scanf("%d %s",&n,a);
for(int i=0;a[i]!='\0';i++)s.insert(a[i]);
int size=s.size(); ans=n;
while(1){
while(R<n&&cnt<size){
if(!f[a[R]])cnt++;
f[a[R++]]++;
}while(f[a[L]]>1)f[a[L++]]--;
if(cnt==size){
ans=min(ans,R-L);
f[a[L++]]--;cnt--;
}if(R==n)break;
}return printf("%d\n",ans),0;
}
评论 (0)
