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

В строке из букв T, U, V, W, X, Y, Z нужно найти минимальную длину непрерывного фрагмента, содержащего не менее 270 букв Z. Подходящий фрагмент существует.

Одного общего числа букв Z недостаточно: одинаковое количество может быть собрано плотно или разделено длинными промежутками. В ответ входят и символы между нужными буквами.

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

Поддерживаем окно от left до right и число Z внутри. Правая граница движется по строке, добавляя новые символы. Как только букв достаточно, запоминаем длину и начинаем сдвигать левую границу, пока условие ещё выполняется.

  1. Добавьте очередной правый символ и увеличьте счётчик, если это Z.
  2. Пока счётчик не меньше порога, обновляйте минимум.
  3. Перед удалением левого символа уменьшите счётчик, если удаляется Z, затем сдвиньте left.
  4. После нарушения условия снова расширяйте окно справа.

Для каждого правого конца так проверяется самый короткий допустимый вариант. Более ранние начала уже длиннее; после удаления нужной Z остаётся ждать следующую. Обе границы двигаются только вперёд, каждая не более n раз. Поэтому вложенный while не делает алгоритм квадратичным: суммарное время — O(n), дополнительная память — O(1).

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

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

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

print("TT" + "Z" * 135 + "T" + "Z" * 135 + "UU")

Вывод

271
Разбор примера по шагам
ФрагментЧисло ZДлина
Вся строка270275
Без TT слева270273
Без UU справа270271
Удалена ещё одна Z269Условие нарушено

Команда «Получить строку ввода» создаёт строку из двух Z-блоков по 135 букв, разделённых одной T, с лишними буквами по краям. Чтобы набрать 270 букв Z, нужны оба блока и разделитель между ними. Удаляем только внешние TT и UU: длина равна 135 + 1 + 135 = 271.

Код на Python и C++

Основной вызов использует порог 270 из условия. Обновление минимума выполняется до удаления левого символа: в этот момент окно ещё допустимо.

import sys


def solve(s, needed=270):
    left = count = 0
    best = len(s) + 1
    for right, ch in enumerate(s):
        count += ch == 'Z'
        while count >= needed:
            best = min(best, right - left + 1)
            count -= s[left] == 'Z'
            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 = 270) {
    int left = 0, count = 0;
    int best = s.size() + 1;
    for (int right = 0; right < (int)s.size(); right++) {
        count += s[right] == 'Z';
        while (count >= needed) {
            best = min(best, right - left + 1);
            count -= s[left] == 'Z';
            left += 1;
        }
    }
    return best;
}

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

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

  • Искать максимальную длину

    Для условия «не менее» вся строка уже подходит, но требуется минимум. Допустимое окно нужно сжимать.

  • Вывести количество Z

    Длина включает все символы между крайними нужными буквами. Разделители внутри окна нельзя пропустить.

  • Удалять по одному символу без цикла

    Слева может быть много лишних символов. Цикл сжатия проверяет все допустимые уменьшения перед следующим расширением.