[TIOJ] 1489. E.核心字串

題目連結:http://tioj.infor.org/problems/1489

---

經典(?的雙指針題，每次右界擴充的時候就判斷一下左界的那個字元是不是出現超過一次了，如果超過一次表示他其實不必要。此外透過計算每個字元出現的次數也可以計算是否26個字母都出現過了，作法大概就是發現這個字元出現了，且之前他沒出現過就讓某一個變數增加一。最後判一下該變數是否為26就好了。

#include <bits/stdc++.h>
using namespace std;

const int INF = 2000000;
const int N = 1000000 + 5;
char str[N];
int cnt[256], c=0;

int main(){
	ios_base::sync_with_stdio(0);cin.tie(0);
	int n;
	while(cin>>n, n){
		fill(cnt, cnt+256, 0);
		c=0;
		cin>>str;
		int ansL=0, ansR=INF;
		int curL=0, curR;
		for(curR=0;curR<n;curR++){
			if(cnt[(unsigned)str[curR]]==0) c++;
			cnt[(unsigned)str[curR]]++;
			while(cnt[(unsigned)str[curL]]>1){
				cnt[(unsigned)str[curL]]--;
				curL++;
			}
			if(c==26){
				if(ansR-ansL > curR-curL){
					ansR=curR;
					ansL=curL;
				}
			}
		}
		if(c<26){
			cout<<"not found\n";
		}else{
			for(int i=ansL;i<=ansR;++i)
				cout<<str[i];
			cout<<'\n';
		}
	}
	return 0;
}