P6878 [JOI 2020 Final] JJOOII 2

A string made up of $K$ consecutive $\tt J$, followed by $K$ consecutive $\tt O$, followed by $K$ consecutive $\tt I$ is called a $K$-th order JOI string. For example, $\tt JJOOII$ is a $2$-th order JOI string. **However, note that the order matters**. For example, $\tt OOJJII$ is not a $2$-th order JOI string. Now, given a string $S$ of length $N$, you may perform the following three operations: - Operation 1: Delete the first character of $S$. - Operation 2: Delete the last character of $S$. - Operation 3: Delete one character of $S$ other than the first and the last. We want to make $S$ become a $K$-th order JOI string using these operations. However, we want to use Operation 3 as few times as possible. So, what is the minimum number of times Operation 3 must be performed to make $S$ into a $K$-th order JOI string? If it is impossible to make it into a $K$-th order JOI string, output $-1$.

The first line contains two integers $N, K$, representing the string length and the order $K$ of the JOI string to construct. The second line contains $N$ characters, representing the string $S$.

Output one integer: the minimum number of times Operation 3 needs to be performed. If it is impossible to make it into a $K$-th order JOI string, output $-1$.

#### Explanation for Sample 1 1. Perform Operation 1 once to get $\tt JIJOIOIIJ$. 2. Perform Operation 2 once to get $\tt JIJOIOII$. 3. Perform Operation 3 once: delete character $2$ to get $\tt JJOIOII$. 4. Perform Operation 3 once: delete character $4$ to get $\tt JJOOII$. #### Explanation for Sample 2 $\tt JJJOOOIII$ is already a $3$-th order JOI string, so no operations are needed. #### Explanation for Sample 3 $\tt IIIOOOJJJ$ cannot be turned into a $1$-st order JOI string, so there is no solution. #### Constraints **This problem uses bundled testdata.** - Subtask 1 (1 pts): $N \le 21$. - Subtask 2 (12 pts): $N \le 3000$. - Subtask 3 (87 pts): No additional constraints. For $100\%$ of the testdata: - $3 \le N \le 2 \times 10^5$. - $1 \le K \le \dfrac{N}{3}$. - $S$ contains only $\tt J$, $\tt O$, $\tt I$, and has length $N$. #### Note Translated from [The 19th Japanese Olympiad in Informatics Final Round](https://www.ioi-jp.org/joi/2019/2020-ho/index.html) [B JJOOII 2](https://www.ioi-jp.org/joi/2019/2020-ho/2020-ho-t2.pdf)。 Translated by ChatGPT 5