Решение: Поиск минимального фрагмента
Текстовый файл состоит из заглавных букв латинского алфавита $A$, $B$, $C$, $D$, $E$ и $F$.
Определите минимальное количество идущих подряд символов в прилагаемом файле, среди которых пара символов $AB$ (в указанном порядке) встречается ровно 220 раз.
Для выполнения этого задания следует написать программу.
Решение по шагам
4 шагаСначала считываем строку из файла и для каждой позиции $i$ проверяем условие: символ в позиции $i$ равен $A$, а следующий символ равен $B$.
Строим префиксные суммы количества вхождений $AB$. Тогда число таких пар на отрезке с границами $l$ и $r$ вычисляется за постоянное время.
Перебираем левую границу фрагмента и с помощью двух указателей либо бинарного поиска находим минимальную правую границу, при которой внутри фрагмента ровно 220 вхождений $AB$.
Среди всех подходящих фрагментов выбираем минимальную длину и выводим её.
Числовой ответ нельзя определить без содержимого прилагаемого текстового файла.
Этот ответ получен в разборе, но не сверен с официальным ключом из банка — проверьте выкладки, прежде чем заучивать результат.
Где здесь ошибаются
Считать перекрывающиеся вхождения неправильно.
Искать только неперекрывающиеся подстроки.
Не учитывать, что пара $AB$ может начинаться на последнем символе выбранного фрагмента и выходить за его границу.
Минимизировать число пар вместо длины фрагмента.