解题思路:分别记录每个 J, O, I 的位置然后遍历 J 的位置查找以每个 J 为起点的可以经过删除区间内元素得到所需串的最短子串,用其长度减去不需要删除的元素个数得到答案
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> P;
const int INF = 0x3f3f3f3f;
const int MAX_N = 2e5 + 10;
const int MOD = 1e9 + 7;
int N, M;
char s[MAX_N];
int cntj[MAX_N], cnto[MAX_N], cnti[MAX_N];
int cj, co, ci;
void solve(){
scanf("%d%d", &N, &M);
scanf("%s", s);
for(int i = 0; i < N; i++){
if(s[i] == 'J') cntj[++cj] = i;
else if(s[i] == 'O') cnto[++co] = i;
else if(s[i] == 'I') cnti[++ci] = i;
}
if(cj < M || co < M || ci < M){
printf("-1"); return;
}
int res = INF, en, lo = 1, li = 1;
for(int i = 1; i <= cj; i++){
if(i + M - 1 > cj) break;
en = cntj[i + M - 1];
while(cnto[lo] < en && lo <= co) ++lo;
if(lo + M - 1 > co) break;
en = cnto[lo + M - 1];
while(cnti[li] < en && li <= ci) ++li;
if(li + M - 1 > ci) break;
en = cnti[li + M - 1];
res = min(res, en - cntj[i] + 1 - 3 * M);
}
if(res == INF) printf("-1");
else printf("%d", res);
}
int main(){
int TCASE = 1;
// scanf("%d", &TCASE);
while(TCASE--) solve();
return 0;
}