[ARC024] C - だれじゃ
[Q] https://atcoder.jp/contests/arc024/tasks/arc024_3
1. alphavetが何文字出現したかをint[]に累積する。
2. map<int[], int> memoで、その累積情報がindexいくつに出現したかメモしていく。
3. K文字見ている時点で
(a) 同じ累積が以前にもあるか
(b) ある場合、今のindex - 以前の出現indexがK以上あるか
を確認し、2つ満たすならYES
実装
int main() {
cincout();
ll N, K;
string S;
cin >> N >> K >> S;
// K文字とって、vectorで累積を保管
vector<ll> V(26, 0);
map<vector<ll>, ll> memo; // 累積, 末端index
// 先頭K-1文字を累積
rep(i, K - 1) { ++V[S[i] - 'a']; }
// しゃくとり
for (ll i = K - 1; i < N; ++i) {
// 末端いれて、
++V[S[i] - 'a'];
// K要素でmemoして
if (memo.count(V) == false)
memo[V] = i;
else {
if (i - memo[V] >= K) {
cout << "YES" << endl;
return 0;
}
}
// 先端削除
--V[S[i - K + 1] - 'a'];
}
cout << "NO" << endl;
}