Мінімальна довжина підрядка (Розбір)

Ідея

Випишемо в окремий масив $p$ позиції всіх букв G у рядку. Нехай кількість таких позицій дорівнює $m$. Оскільки ми виписуємо позиції зліва направо, масив $p$ вже буде відсортованим.

Нам потрібно вибрати $k$ букв G, які містяться у якомога коротшому відрізку. В оптимальній відповіді ці $k$ букв будуть послідовними в масиві $p$. Тому достатньо перебрати всі групи з $k$ послідовних елементів.

Для групи

найкоротший відрізок, який містить усі ці букви, починається в p_i та закінчується в p_{i+k-1}. Тому його довжина визначається як

Отже, відповідь дорівнює

Загальна асимптотика — $O(n)$.