Решение: Минимальный фрагмент с W
Текстовый файл состоит из символов $T$, $U$, $V$, $W$, $X$, $Y$ и $Z$. Определите в прилагаемом файле минимальное количество идущих подряд символов (длину непрерывной подпоследовательности), среди которых символ $W$ встречается не менее 240 раз. Для выполнения этого задания следует написать программу.
Решение по шагам
4 шагаСчитываем строку из файла и рассматриваем её как последовательность символов.
Двигаем правую границу окна слева направо. При встрече символа $W$ увеличиваем счётчик символов $W$.
$$count_W \mathrel{+}= 1$$Когда в окне становится не менее 240 символов $W$, сдвигаем левую границу вправо, пока условие сохраняется. На каждом шаге обновляем минимальную длину окна.
$$L = right - left + 1$$Каждый символ добавляется в окно и удаляется из него не более одного раза, поэтому алгоритм работает за линейное время.
$$O(n)$$Программа выводит минимальную длину непрерывной подпоследовательности, содержащей не менее 240 символов W.
Этот ответ получен в разборе, но не сверен с официальным ключом из банка — проверьте выкладки, прежде чем заучивать результат.
Где здесь ошибаются
Перебирать все пары границ и получить квадратичную сложность.
Не уменьшать счётчик при удалении символа W из левой части окна.
Искать только первый подходящий фрагмент, не проверяя возможность его дальнейшего сокращения.