【題解】LibreOJ #3253. 「JOI 2020 Final」JJOOII 2

#include <iostream>
using namespace std;

const int maxn = 200005;
string s;
int n, k, j[maxn], o[maxn], I[maxn];

int main() {
    cin >> n >> k >> s;
    int l = 0, cnt = 0;

    for (int i = 0; i < n; i++) {
        if (s[i] == 'J')
            cnt++;

        if (cnt < k) {
            j[i] = -1;
            continue;
        }

        while (cnt > k) {
            if (s[l] == 'J')
                cnt--;

            l++;
        }

        while (s[l] != 'J')
            l++;

        j[i] = l;
    }

    l = 0;
    cnt = 0;

    for (int i = 0; i < n; i++) {
        if (s[i] == 'O')
            cnt++;

        if (cnt < k) {
            o[i] = -1;
            continue;
        }

        while (cnt > k) {
            if (s[l] == 'O')
                cnt--;

            l++;
        }

        while (s[l] != 'O')
            l++;

        o[i] = l;
    }

    l = 0;
    cnt = 0;

    for (int i = 0; i < n; i++) {
        if (s[i] == 'I')
            cnt++;

        if (cnt < k) {
            I[i] = -1;
            continue;
        }

        while (cnt > k) {
            if (s[l] == 'I')
                cnt--;

            l++;
        }

        while (s[l] != 'I')
            l++;

        I[i] = l;
    }

    int ans = maxn;

    for (int i = 0; i < n; i++) {
        int now;

        if (I[i] == -1)
            continue;

        now = I[i];

        if (now - 1 < 0 || o[now - 1] == -1)
            continue;

        now = o[now - 1];

        if (now - 1 < 0 || j[now - 1] == -1)
            continue;

        now = j[now - 1];
        ans = min(ans, i - now + 1 - k * 3);
    }

    if (ans == maxn)
        cout << -1 << "\n";
    else
        cout << ans << "\n";
}