Сформулируйте результат до выбора переменных
Для строки AABBBBAACCC ответ равен четырём: самая длинная серия состоит из четырёх символов B. Количество всех букв A здесь не относится к вопросу, потому что они образуют разные фрагменты. Важно различать общую частоту символа и длину непрерывной серии. До программирования решите несколько маленьких примеров вручную. Они помогут увидеть, что алгоритм должен помнить при чтении очередного знака. Если условие задачи отличается, например допускает чередование, правила перехода тоже будут другими.
Храните текущую серию и лучший результат
При чтении слева направо достаточно знать предыдущий символ, длину текущей серии и максимальную найденную длину. Если новый символ совпадает с предыдущим, текущая серия увеличивается. Если отличается, начинается новая серия длины один. После обработки каждого символа текущую длину сравнивают с максимумом. Такой порядок позволяет не забыть серию в конце строки: она учитывается ещё при чтении её последнего элемента. Начальные значения нужно выбрать так, чтобы первый символ создавал корректную серию, а пустая последовательность обрабатывалась осмысленно, если она допустима.
Проверяйте инвариант после каждого шага
Инвариантом называют утверждение, которое остаётся верным на определённой границе каждого шага алгоритма. Здесь после обработки очередного символа текущая длина равна длине серии, заканчивающейся на нём, а максимум отражает все уже просмотренные серии. Это объясняет, почему не нужно хранить каждую найденную цепочку. Если после смены символа текущая длина обнулилась и больше не увеличилась на этом же шаге, инвариант нарушен: новый знак уже прочитан и должен учитываться. Такая проверка помогает искать логические ошибки точнее, чем случайная перестановка команд.
Малые тесты обнаруживают большие недочёты
Используйте строку из одного символа, строку без одинаковых соседей, полностью одинаковые символы и случай, где лучшая серия стоит в конце. Последний тест особенно полезен, если максимум обновляется только при смене знака. Для файла отдельно проверьте, относится ли перевод строки к данным и как устроен ввод. Один проход обрабатывает каждый символ один раз, поэтому число основных действий растёт пропорционально длине последовательности. Но корректность важнее этой оценки: быстрый алгоритм с неверной обработкой границы всё равно решает другую задачу.
Попробуйте на практике
Вручную выполните алгоритм и проверьте его на граничных примерах.
- Запишите AABBBBAACCC и подготовьте три колонки состояния: предыдущий символ, текущая длина и максимум. Начните с пустого обработанного префикса.
- Пройдите строку по одному символу, после каждого шага обновляя текущую серию и лучший результат. Проверьте инвариант в момент перехода от B к A.
- Повторите разбор для A, ABC и ABBBB. Объясните, почему последняя серия обязательно попадает в итог.
- Придумайте ошибочную версию, обновляющую максимум только при смене символа. Найдите короткий пример, на котором она даёт неправильный ответ.
Как проверить результат. Для основной строки получено четыре, а граничные тесты объяснены состояниями алгоритма. Последняя серия учитывается без надежды на появление следующего отличающегося символа.
Частые вопросы
Нужно ли сохранять все фрагменты в отдельный список?
Для этой задачи нет: достаточно текущего состояния и лучшей длины. Другой вопрос, например вывод всех фрагментов, может потребовать дополнительных данных.
Готовый шаблон подходит к любой задаче со строкой?
Нет. Сначала проверяют условие допустимости фрагмента и смысл результата. Похожий вид входа не означает одинаковый алгоритм.
Самостоятельный разбор темы. Содержание конкретной обучающей программы здесь не представлено.