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

В строке из букв X, Y, Z найдите самый длинный непрерывный фрагмент без полного вхождения XZZY. Части этой комбинации на краях разрешены: например, XZZ и ZZY сами по себе подходят.

Удаление всей найденной комбинации или разбиение строки по ней теряет допустимые символы. Нужно исключить только возможность целиком включить запрещённый фрагмент.

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

Будем двигать правую границу и хранить минимальную допустимую левую. Если на позиции right заканчивается запрещённое слово длины четыре, его начало равно right - 3. Чтобы слово не вошло целиком, начало окна должно стать хотя бы на единицу правее: left = right - 2.

Для общей формулы используем left = max(left, start + 1). Левая граница никогда не идёт назад. Оставшийся суффикс запрещённого слова разрешён: он уже не содержит полного вхождения.

  1. Просмотрите все правые концы окна.
  2. Сравните четыре последних символа с XZZY, если их уже достаточно.
  3. При совпадении сдвиньте левую границу за начало найденного слова.
  4. Обновите максимум длиной right - left + 1.

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

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

Ввод

YXZZYXZZ

Вывод

6
Разбор примера по шагам
Правый конецЛевая границаДопустимый фрагмент
30YXZZ
4: завершилось XZZY2ZZY
72ZZYXZZ

Вхождение XZZY занимает позиции 1–4. Достаточно исключить его первую X, сдвинув начало на позицию 2. Полученный фрагмент ZZYXZZ содержит обе неполные части по краям, но не содержит полной комбинации; его длина равна шести.

Код на Python и C++

После совпадения пропускается начало запрещённого слова, а не все его символы. Срез имеет постоянную длину четыре, так что перебор остаётся линейным.

В C++ вместо среза — s.compare(start, 4, pattern) == 0: четыре символа сравниваются на месте, новая строка не создаётся.

import sys


def solve(s):
    pattern = 'XZZY'
    left = best = 0
    for right in range(len(s)):
        start = right - len(pattern) + 1
        if start >= 0 and s[start:right + 1] == pattern:
            left = max(left, start + 1)
        best = max(best, right - left + 1)
    return best

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

int solve(const string& s) {
    const string pattern = "XZZY";
    int n = s.size(), len = pattern.size();
    int left = 0, best = 0;
    for (int right = 0; right < n; right++) {
        int start = right - len + 1;
        if (start >= 0 && s.compare(start, len, pattern) == 0)
            left = max(left, start + 1);
        best = max(best, right - left + 1);
    }
    return best;
}

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

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

  • Выбросить запрещённое слово целиком

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

  • Использовать split по запрещённой комбинации

    Так исчезает возможность использовать суффикс одного вхождения и префикс следующего в общей допустимой подстроке.

  • Забыть единицу в длине окна

    При включённых границах количество символов равно right - left + 1, а не разности индексов.