#include <bits/stdc++.h>
using namespace std;
const int N = 2e5 + 5;
int get(char ch) {
if(ch == 'J') return 0;
if(ch == 'O') return 1;
return 2;
}
int vis[N][4], ans=1e9;
vector<int> G[N];
void dfs(int u, int t, int l) {
if(vis[u][t]) return ;
if(t == 3) {
ans = min(ans, u-l+1);
return ;
}
for(int v : G[u]) dfs(v, t+1, l);
}
signed main() {
int n, k; cin >> n >> k;
string s; cin >> s;
s = "." + s;
vector<int> pos[3];
for(int i=1; i<=n; i++)
pos[get(s[i])].push_back(i);
for(int i=0; i<3; i++) {
if(pos[i].size() < k) {
cout << -1 << '\n';
return 0;
}
}
for(int i=0; i+k-1<pos[2].size(); i++)
G[pos[2][i]].push_back(pos[2][i+k-1]);
for(int t=0; t<2; t++) {
for(int i=0; i+k-1<pos[t].size(); i++) {
auto p = lower_bound(pos[t+1].begin(), pos[t+1].end(), pos[t][i+k-1]);
if(p != pos[t+1].end())
G[pos[t][i]].push_back(*p);
}
}
for(int i=1; i<=n; i++)
if(s[i] == 'J' && !vis[i][0]) dfs(i, 0, i);
cout << (ans == 1e9 ? -1 : ans - 3*k) << '\n';
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |