They Are Everywhere [Codeforces 364 : Div2 C, Div1 A]

問題

http://codeforces.com/contest/701/problem/C

n文字の文字列がある。
これの連続する部分文字列の中で（元の文字列について）全種類の文字が含まれている文字列の中で最小の文字列長は？

1 <= n <= 10^5

考察

1. 全部の連続する部分文字列を考えると O(n^2) で無理
2. 片方だけ固定して、にぶたんで条件をみたす最短の部分列取ればいいんじゃない？
3. imos法とか使ってカウントすれば行けそうじゃない？
4. こんな感じに全探索から考えてくといいです
5. これで実装するとWAくらいました（この解法でも解けるはず）

6. 文字列で10^5でDiv1 Cなので、若干、尺取り法かな感がある
7. 尺取りかな―と考えていると、尺取りでした
8. 順番に尺取りで範囲を変えていって、範囲の最小とってやればいいです

9. 今回は文字列の扱いが少し厄介ですが、mapを使えば比較的さくっと書けます

実装

http://codeforces.com/contest/701/submission/19340341

int n;
string s;
//-----------------------------------------------------------------
#define INF INT_MAX/2
int main()
{
	cin >> n >> s;

	map<char, int> m;
	rep(i, 0, n) m[s[i]] = 0;
	int nn = m.size();

	int ans = INF;
	int idx = 0;
	rep(i, 0, n + 1) {
		m[s[i]]++;

		bool ok = true;
		for (auto p : m) if (p.second == 0) ok = false;

		while (idx <= i) {
			if (!ok) break;
			ans = min(ans, i - idx + 1);

			m[s[idx]]--;
			idx++;

			for (auto p : m) if (p.second == 0) ok = false;
		}
	}

	cout << ans << endl;
}