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

Нужен самый длинный фрагмент, содержащий ровно 80 букв Y и не менее 90 вхождений комбинации 2025. Все четыре символа каждого учтённого вхождения должны целиком находиться в том же фрагменте.

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

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

Будем держать самое широкое окно с не более чем 80 буквами Y для каждого правого конца. При добавлении символа справа увеличиваем счётчик Y, если нужно. Если завершилась комбинация 2025, целиком лежащая в окне, увеличиваем счётчик комбинаций.

Пока Y слишком много, сдвигаем левую границу. Перед удалением левого символа проверяем две вещи: является ли он Y и начинается ли с него полное вхождение 2025. Во втором случае уменьшаем счётчик комбинаций, потому что после сдвига их первая цифра окажется за границей окна.

  1. Добавьте правый символ и возможное новое полное вхождение.
  2. Уберите слева избыток букв Y, одновременно корректируя оба счётчика.
  3. Если Y ровно 80, а комбинаций не менее 90, обновите максимум длины.

Почему не надо сжимать окно из-за недостатка комбинаций? Взять более короткий фрагмент с тем же правым концом не добавит ни одной комбинации. Если в самом широком допустимом окне их мало, подходящего более короткого окна тоже нет. Если Y меньше 80, сдвиг начала также не поможет. Значит, проверять нужно только поддерживаемое окно.

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

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

Получить строку ввода (Python)

print("A" + "2025" * 91 + "Y" * 81 + "B")

Вывод

445
Разбор примера по шагам
ОкноYВхождения 2025Длина
Вся строка8191447: слишком много Y
Позиции 0–4448091445: подходит
Позиции 366–44680081: комбинаций не хватает

Созданная строка содержит 91 повторение 2025, затем 81 букву Y, а по краям A и B. Подходит префикс до восьмидесятой Y включительно: 1 + 4 × 91 + 80 = 445. При добавлении следующей Y левая граница уйдёт за первую Y и потеряет все комбинации. Длинный суффикс с нужным числом Y не подходит без достаточного числа 2025.

Код на Python и C++

Параметры основного вызова — 80 и 90. Счётчик вхождений обновляется на обеих границах; выход первой цифры вхождения за левую границу исключает его целиком.

В C++ вхождение 2025 с позиции start проверяет s.compare(start, 4, "2025") == 0.

import sys


def solve(s, needed_y=80, needed_pattern=90):
    left = ys = occurrences = best = 0
    for right, ch in enumerate(s):
        ys += ch == 'Y'
        start = right - 3
        if start >= left and s[start:right + 1] == '2025':
            occurrences += 1
        while ys > needed_y:
            ys -= s[left] == 'Y'
            if left + 3 <= right and s[left:left + 4] == '2025':
                occurrences -= 1
            left += 1
        if ys == needed_y and occurrences >= needed_pattern:
            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, int needed_y = 80, int needed_pattern = 90) {
    int left = 0, ys = 0, occurrences = 0, best = 0;
    for (int right = 0; right < (int)s.size(); right++) {
        ys += s[right] == 'Y';
        int start = right - 3;
        if (start >= left && s.compare(start, 4, "2025") == 0)
            occurrences += 1;
        while (ys > needed_y) {
            ys -= s[left] == 'Y';
            if (left + 3 <= right && s.compare(left, 4, "2025") == 0)
                occurrences -= 1;
            left += 1;
        }
        if (ys == needed_y && occurrences >= needed_pattern)
            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;
}

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

  • Требовать ровно 90 комбинаций

    Для 2025 условие задаёт нижний порог. Окно с большим числом комбинаций тоже может быть ответом.

  • Считать комбинации во всей строке

    Оба ограничения относятся к одному окну. Комбинации за его границами не помогают выполнить условие.

  • Забыть удалить ушедшее вхождение

    Если левая граница прошла первую цифру комбинации, она уже не целиком внутри. При сжатии обновляйте счётчик комбинаций.

  • Перебирать каждое начало отдельно

    Повторное расширение окна для всех начал даёт квадратичный проход. Обе границы можно перемещать только вперёд.