Шешімі: Максимальная допустимая последовательность
Текстовый файл состоит не более чем из 1 200 000 символов K, L, M и N. Определите максимальное количество идущих подряд символов, среди которых нет символов K и M, стоящих рядом. Для выполнения этого задания следует написать программу.
Шешім по шагам
4 қадамПоследовательно просматриваем символы файла, храня предыдущий символ и длину текущей последовательности.
Если текущий и предыдущий символы образуют пару KM или MK, текущую длину устанавливаем равной 1; иначе увеличиваем её на 1.
После каждого шага сравниваем текущую длину с максимальной. Одного прохода по файлу достаточно, поэтому сложность алгоритма составляет O(n).
Для данного файла максимальная длина подходящей последовательности равна 112.
Где здесь ошибаются
Считать недопустимыми все символы K и M, хотя запрещены только соседние пары KM и MK.
Проверять только пару KM и не учитывать пару MK.
После обнаружения запрещённой пары начинать новую последовательность не с последнего символа.