Решение: Максимальная подпоследовательность
Текстовый файл состоит из символов $T$, $U$, $V$, $W$, $X$, $Y$ и $Z$. Определите в прилагаемом файле максимальное количество идущих подряд символов (длину непрерывной подпоследовательности), среди которых символ $W$ встречается не более 130 раз. Для выполнения этого задания следует написать программу.
Решение по шагам
4 шагаЗадачу решаем одним проходом по строке с помощью двух границ окна. При добавлении очередного символа увеличиваем счётчик символов $W$, если добавлен именно $W$.
$$count_W \mathrel{+}= (s[r] = W)$$Если в текущем окне оказалось более 130 символов $W$, сдвигаем левую границу вправо, уменьшая счётчик при удалении символа $W$.
$$count_W > 130 \Rightarrow l \mathrel{+}= 1$$После восстановления ограничения вычисляем длину текущего окна и сравниваем её с найденным максимумом.
$$length = r - l + 1$$При обработке приложенного файла максимальная длина допустимой непрерывной подпоследовательности равна 237.
$$max\_length = 237$$Где здесь ошибаются
Искать только самый длинный фрагмент с ровно 130 символами $W$, хотя допускается не более 130.
Не сдвигать левую границу окна после превышения допустимого количества символов $W$.
Пересчитывать каждый фрагмент заново и получать медленный алгоритм.