题目大意

给定一个长度为 $N$ 的字符串 $S$，由字符 $\texttt{J}$、$\texttt{O}$、$\texttt{I}$ 组成。我们可以进行三种操作：

1. 删除开头字符
2. 删除结尾字符
3. 删除中间任意字符（不能是开头或结尾）

目标是通过这些操作将 $S$ 变成 $K$ 级 JOI-串，即由 $K$ 个连续的 $\texttt{J}$、$K$ 个连续的 $\texttt{O}$ 和 $K$ 个连续的 $\texttt{I}$ 连接而成的字符串（总长度为 $3K$）。

要求最小化操作 3 的使用次数，如果无法实现则输出 $-1$。

问题分析

关键观察

1. 操作性质：操作 1 和 2 只能删除两端字符，操作 3 可以删除中间任意字符。这意味着我们可以保留原字符串中一个连续的 $3K$ 长度的子串，然后通过操作 3 删除其中不符合 JOI-串格式的字符。

2. JOI-串结构：目标字符串的形式为 $\underbrace{\texttt{J}\cdots\texttt{J}}_{K\text{个}}\underbrace{\texttt{O}\cdots\texttt{O}}_{K\text{个}}\underbrace{\texttt{I}\cdots\texttt{I}}_{K\text{个}}$。

3. 问题转化：我们需要在 $S$ 中找到一个长度为 $3K$ 的连续子串，使得通过最少的操作 3（即删除最少的字符）能够将其变成 JOI-串。

核心思路

对于每个可能的起始位置 $i$，考虑长度为 $3K$ 的子串 $S[i:i+3K]$，我们需要计算将其变成 JOI-串所需删除的字符数量。

JOI-串要求：

• 前 $K$ 个字符都是 $\texttt{J}$
• 中间 $K$ 个字符都是 $\texttt{O}$
• 后 $K$ 个字符都是 $\texttt{I}$

因此，对于子串 $S[i:i+3K]$：

• 需要删除其中所有不是 $\texttt{J}$ 的字符（在前 $K$ 个位置中）
• 需要删除其中所有不是 $\texttt{O}$ 的字符（在中间 $K$ 个位置中）
• 需要删除其中所有不是 $\texttt{I}$ 的字符（在后 $K$ 个位置中）

算法设计

1. 预处理前缀和：

   • 定义三个数组 $preJ[i]$、$preO[i]$、$preI[i]$，分别表示前 $i$ 个字符中 $\texttt{J}$、$\texttt{O}$、$\texttt{I}$ 的数量。

2. 滑动窗口计算：

   • 对于每个起始位置 $i$（$0 \leq i \leq N-3K$），计算将子串 $S[i:i+3K]$ 变成 JOI-串所需的操作次数：

     操作次数 = (K - 前K个中J的数量) + (K - 中间K个中O的数量) + (K - 后K个中I的数量)
     

   • 使用前缀和数组可以 $O(1)$ 计算每个区间的字符数量。

3. 寻找最小值：

   • 遍历所有可能的起始位置，记录最小的操作次数。
   • 如果所有位置都无法满足要求（即最小操作次数为无穷大），输出 $-1$。

时间复杂度

• 预处理前缀和：$O(N)$
• 滑动窗口遍历：$O(N)$
• 总时间复杂度：$O(N)$，可以处理 $N \leq 2 \times 10^5$ 的数据规模。

边界情况

1. 当 $K = 1$ 时，目标字符串为 $\texttt{JOI}$。
2. 当 $N = 3K$ 时，只能选择整个字符串。
3. 当字符串中某种字符数量不足 $K$ 时，肯定无解。

代码实现要点

// 伪代码
1. 读取 N, K 和字符串 S
2. 预处理前缀和数组 preJ, preO, preI
3. 初始化答案 ans = INF
4. for i从0到N-3K:
   - 计算前K个位置中J的数量 = preJ[i+K] - preJ[i]
   - 计算中间K个位置中O的数量 = preO[i+2K] - preO[i+K]  
   - 计算后K个位置中I的数量 = preI[i+3K] - preI[i+2K]
   - 操作次数 = (K - J_count) + (K - O_count) + (K - I_count)
   - 更新 ans = min(ans, 操作次数)
5. 如果 ans == INF 输出 -1，否则输出 ans

总结

本题的关键在于将复杂的操作问题转化为在字符串中寻找最优子串的问题。通过前缀和预处理和滑动窗口技巧，我们可以在线性时间内解决问题。这种"最小修改使得子串满足特定模式"的思路在字符串处理中很常见，值得掌握。