首页 > 代码库 > Codeforces 701C They Are Everywhere（Two pointers+STL）
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; }
Codeforces 701C They Are Everywhere（Two pointers+STL）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。