import java.util.*;
import java.io.*;
public class ho_t2 {
final static int MOD = 1000000007;
final static int intMax = 1000000000;
final static int intMin = -1000000000;
final static int[] dx = { 0, 0, -1, 1 };
final static int[] dy = { -1, 1, 0, 0 };
static int T;
static class Reader {
final private int BUFFER_SIZE = 1 << 16;
private DataInputStream din;
private byte[] buffer;
private int bufferPointer, bytesRead;
public Reader() {
din = new DataInputStream(System.in);
buffer = new byte[BUFFER_SIZE];
bufferPointer = bytesRead = 0;
}
public Reader(String file_name) throws IOException {
din = new DataInputStream(new FileInputStream(file_name));
buffer = new byte[BUFFER_SIZE];
bufferPointer = bytesRead = 0;
}
public String readLine() throws IOException {
byte[] buf = new byte[360]; // line length
int cnt = 0, c;
while ((c = read()) != -1) {
if (c == '\n')
break;
buf[cnt++] = (byte) c;
}
return new String(buf, 0, cnt);
}
public int nextInt() throws IOException {
int ret = 0;
byte c = read();
while (c <= ' ')
c = read();
boolean neg = (c == '-');
if (neg)
c = read();
do {
ret = ret * 10 + c - '0';
} while ((c = read()) >= '0' && c <= '9');
if (neg)
return -ret;
return ret;
}
public long nextLong() throws IOException {
long ret = 0;
byte c = read();
while (c <= ' ')
c = read();
boolean neg = (c == '-');
if (neg)
c = read();
do {
ret = ret * 10 + c - '0';
} while ((c = read()) >= '0' && c <= '9');
if (neg)
return -ret;
return ret;
}
public double nextDouble() throws IOException {
double ret = 0, div = 1;
byte c = read();
while (c <= ' ')
c = read();
boolean neg = (c == '-');
if (neg)
c = read();
do {
ret = ret * 10 + c - '0';
} while ((c = read()) >= '0' && c <= '9');
if (c == '.') {
while ((c = read()) >= '0' && c <= '9') {
ret += (c - '0') / (div *= 10);
}
}
if (neg)
return -ret;
return ret;
}
private void fillBuffer() throws IOException {
bytesRead = din.read(buffer, bufferPointer = 0, BUFFER_SIZE);
if (bytesRead == -1)
buffer[0] = -1;
}
private byte read() throws IOException {
if (bufferPointer == bytesRead)
fillBuffer();
return buffer[bufferPointer++];
}
public void close() throws IOException {
if (din == null)
return;
din.close();
}
}
static int N, K;
static String s;
static TreeSet<letter> J, O, I;
static int numj, numo, numi;
static int[] inds;
static int p1, p2;
static void search(int cur, int amtcur) {
while(p2 < N) {
int let = s.charAt(p2) == 'J' ? 0 : s.charAt(p2) == 'O' ? 1 : 2;
if(cur == 0) {
if(let == 0) {
++amtcur;
J.add(new letter(p2, ++numj));
inds[p2] = numj;
}
else if(let == 1) {
O.add(new letter(p2, ++numo));
inds[p2] = numo;
}
else {
I.add(new letter(p2, ++numi));
inds[p2] = numi;
}
if(amtcur == K) {
amtcur = 0;
++cur;
}
}
else if(cur == 1) {
if(let == 0) {
J.add(new letter(p2, ++numj));
inds[p2] = numj;
}
else if(let == 1) {
++amtcur;
O.add(new letter(p2, ++numo));
inds[p2] = numo;
}
else {
I.add(new letter(p2, ++numi));
inds[p2] = numi;
}
if(amtcur == K) {
amtcur = 0;
++cur;
}
}
else {
if(let == 0) {
J.add(new letter(p2, ++numj));
inds[p2] = numj;
}
else if(let == 1) {
O.add(new letter(p2, ++numo));
inds[p2] = numo;
}
else {
++amtcur;
I.add(new letter(p2, ++numi));
inds[p2] = numi;
}
if(amtcur == K) break;
}
++p2;
}
}
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken());
K = Integer.parseInt(st.nextToken());
s = br.readLine();
J = new TreeSet<letter>((a, b) -> a.pos - b.pos);
O = new TreeSet<letter>((a, b) -> a.pos - b.pos);
I = new TreeSet<letter>((a, b) -> a.pos - b.pos);
numj = 0; numo = 0; numi = 0;
p1 = 0; p2 = 0;
inds = new int[N];
search(0, 0);
if(p2 == N) {
System.out.println(-1);
}
else {
int mn = p2 + 1;
while(true) {
int let = s.charAt(p1) == 'J' ? 0 : s.charAt(p1) == 'O' ? 1 : 2;
if(let == 0) {
J.remove(new letter(p1, inds[p1]));
--numj;
if(numj < K) {
search(0, numj);
if(p2 == N) break;
}
else {
int l = 0, r = N;
while(l < r) {
int mid = l + (r - l) / 2;
letter md = new letter(mid, 0);
int sz = J.headSet(md, false).size();
if(sz >= K) {
r = mid;
}
else {
l = mid + 1;
}
}
int amtlefti = I.tailSet(new letter(l, 0), true).size();
if(amtlefti < K) {
search(1, amtlefti);
if(p2 == N) break;
}
else {
l = 0; r = N;
while(l < r) {
int mid = l + (r - l) / 2;
letter md = new letter(mid, 0);
int sz = I.headSet(md, false).size();
if(sz >= K) {
r = mid;
}
else {
l = mid + 1;
}
}
int amtlefto = O.tailSet(new letter(l, 0), true).size();
if(amtlefto < K) {
search(2, amtlefto);
if(p2 == N) break;
}
}
}
}
else {
if(let == 1) {
O.remove(new letter(p1, inds[p1]));
--numo;
}
else {
I.remove(new letter(p1, inds[p1]));
--numi;
}
}
++p1;
mn = Math.min(mn, p2 - p1 + 1);
}
System.out.println(mn - 3 * K);
}
// in.close();
}
static class letter{
int pos, ind;
letter(int p, int i){
pos = p; ind = i;
}
}
}
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
262 ms |
16896 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
262 ms |
16896 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
262 ms |
16896 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
