Решение: Максимальная цепочка пар
Текстовый файл состоит из символов $A$, $B$ и $D$. Определите максимальное количество идущих подряд пар символов $BA$ или $DA$ в прилагаемом файле. Искомая подпоследовательность должна состоять только из пар $BA$, только из пар $DA$ или из пар $BA$ и $DA$ в произвольном порядке следования этих пар.
Для решения задачи напишите программу, которая считывает содержимое прилагаемого файла и выводит найденное максимальное количество пар.
Решение по шагам
4 шагаИскомая последовательность разбивается на непересекающиеся пары, поэтому после проверки пары нужно переходить к следующему символу через два места.
Пара является допустимой, если её первый символ — $B$ или $D$, а второй символ — $A$.
$$s[i] \in \{B,D\} \land s[i+1] = A$$При обнаружении допустимой пары увеличиваем длину текущей цепочки и обновляем максимум. При обнаружении недопустимой пары начинаем новую цепочку.
$$current = current + 1$$Алгоритм выполняет один проход по строке и работает за линейное время.
$$O(n)$$Вывести максимальное количество последовательных непересекающихся пар $BA$ или $DA$, найденных в файле.
Этот ответ получен в разборе, но не сверен с официальным ключом из банка — проверьте выкладки, прежде чем заучивать результат.
Где здесь ошибаются
Проверять пары со сдвигом на один символ вместо перехода через два символа.
Считать только одинаковые пары $BA$ или только одинаковые пары $DA$, хотя их можно чередовать.
Не обнулять текущую длину цепочки после недопустимой пары.
Не учитывать последнюю пару, если строка заканчивается на символе $A$.