Spoiler Alert

Hint 1

• Cách đơn giản nhất là duyệt qua từng đoạn \(1 \leq i \leq j \leq n\)

Gọi số lượng O trong đoạn là cntO

Gọi số lượng R trong đoạn là cntR

Chọn đoạn dài nhất thỏa cntO = cntR * k

Hint 2

• Dùng mảng cộng dồn ta có thể tính số lượng O, R trong \(O(1)\)

Gọi f(n, c) là số lượng kí tự c trong đoạn [1, n]

Có số lượng kí tự c trong đoạn [l, r] là f(r, c) - f(l - 1, c)

Hint 3

• Ta có thể tìm trước i một đoạn nào đó mà sau khi loại nó ra ta sẽ được kết quả cntO = cntR * k

Gọi cntO là số lượng kí tự O tính từ 1 -> i

Gọi cntR là số lượng kí tự R tính từ 1 -> i

Nếu cntO = cntR * k sẵn rồi thì cập nhật res = i

Nếu cntO - cntR * k tồn tại thì cập nhật res = max(res, vị trí hiện tại - vị trí cuối đoạn con đó)

Nếu cntO - cntR * k không tồn tại, thì ta đánh dấu vị trí cuối của nó là i

Reference AC code | O(n) time | O(1) auxiliary space | Online Solving, STL, Equalsum-problem ???

int main()
{
    int n, k;
    cin >> n >> k;

    char c;
    while (c = getchar(), c != 'O' && c != 'R');

    unordered_map<long long, int> M;
    int res = 0;
    int cntO = 0, cntR = 0;
    for (int i = 1; i <= n; ++i, c = getchar())
    {
        (c == 'O') ? cntO++ : cntR++;
        long long t = 1LL * cntO - 1LL * cntR * k;

        if (t == 0) res = i;
        if (M[t] != 0)
            res = max(res, i - M[t]);
        else 
            M[t] = i;
    }

    cout << res;
}