Что спрашивают

Нужен самый длинный фрагмент, продолжающий цикл K → L → M → N → K. В начале и конце группа может быть неполной, но внутри должна присутствовать хотя бы одна полная комбинация KLMN.

Одна лишь длина от четырёх не гарантирует полную группу. Например, LMNK соблюдает цикл, но не содержит KLMN. В связанной задаче подходящий фрагмент существует.

Приём решения

Сначала выделяем максимальные участки, на которых каждый символ является правильным продолжением предыдущего. Для этого зададим словарь следующей буквы. Если переход нарушен, текущий символ начинает новый участок, а признак наличия полной группы сбрасывается.

Полную группу удобно обнаружить по её последней букве. Если текущий участок соблюдает цикл, заканчивается на N и имеет длину не меньше четырёх, последние четыре символа обязательно KLMN. После этого весь участок, включая его неполные края, допустим.

  1. Храните начало текущего циклического участка и флаг complete.
  2. При неправильном соседстве перенесите начало на текущую позицию и сбросьте флаг.
  3. При N и достаточной длине установите флаг.
  4. Обновляйте максимум только при истинном флаге, используя полную длину участка.

Неполные края не нарушают правильный порядок и только увеличивают ответ, поэтому после появления полной группы их не нужно обрезать. В ответе требуется количество символов, а не число целых групп. Время — O(n), дополнительная память состояния — O(1).

Разбор на примере

Ввод

LMNKLMKLMN

Вывод

4
Разбор примера по шагам
УчастокДлинаЕсть полная KLMN
LMNKLM6Нет
Новая K после MНачало нового участкаФлаг сброшен
KLMN4Да

Первый циклический участок LMNKLM длиннее четырёх, но его единственная K не успевает получить продолжение LMN. Следующая K нарушает переход после M и начинает новый участок KLMN. Только он подходит, поэтому ответ — четыре. В другом входе после полной группы разрешено продолжать цепочку, например до KLMNKL.

Код на Python и C++

Проверка полной группы делается внутри текущего правильного участка. Значение флага нельзя переносить через разрыв последовательности.

В C++ словарь следующей буквы — map<char, char>.

import sys


def solve(s):
    successor = {'K': 'L', 'L': 'M', 'M': 'N', 'N': 'K'}
    start = best = 0
    complete = False
    for i, ch in enumerate(s):
        if i > 0 and successor[s[i - 1]] != ch:
            start = i
            complete = False
        if ch == 'N' and i - start + 1 >= 4:
            complete = True
        if complete:
            best = max(best, i - start + 1)
    return best

if __name__ == '__main__':
    print(solve(sys.stdin.readline().rstrip('\r\n')))
#include <algorithm>
#include <iostream>
#include <map>
#include <string>
using namespace std;

int solve(const string& s) {
    map<char, char> successor = {{'K', 'L'}, {'L', 'M'}, {'M', 'N'}, {'N', 'K'}};
    int start = 0, best = 0;
    bool complete = false;
    for (int i = 0; i < (int)s.size(); i++) {
        char ch = s[i];
        if (i > 0 && successor[s[i - 1]] != ch) {
            start = i;
            complete = false;
        }
        if (ch == 'N' && i - start + 1 >= 4)
            complete = true;
        if (complete)
            best = max(best, i - start + 1);
    }
    return best;
}

int main() {
    string s;
    getline(cin, s);
    if (!s.empty() && s.back() == '\r')
        s.pop_back();
    cout << solve(s) << endl;
}

Типичные ошибки

  • Принять любой длинный циклический участок

    Даже фрагмент длины шесть может не содержать KLMN из-за смещённого начала. Наличие полной группы проверяется отдельно.

  • Считать только полные группы

    Условие допускает неполную группу на каждом краю. После появления полного KLMN учитывайте весь текущий участок.

  • Делить найденную длину на четыре

    Требуется число символов. Деление вернёт количество групп и изменит смысл ответа.