Что спрашивают
В строке из букв T, U, V, W, X, Y, Z нужно найти минимальную длину непрерывного фрагмента, содержащего не менее 270 букв Z. Подходящий фрагмент существует.
Одного общего числа букв Z недостаточно: одинаковое количество может быть собрано плотно или разделено длинными промежутками. В ответ входят и символы между нужными буквами.
Приём решения
Поддерживаем окно от left до right и число Z внутри. Правая граница движется по строке, добавляя новые символы. Как только букв достаточно, запоминаем длину и начинаем сдвигать левую границу, пока условие ещё выполняется.
- Добавьте очередной правый символ и увеличьте счётчик, если это Z.
- Пока счётчик не меньше порога, обновляйте минимум.
- Перед удалением левого символа уменьшите счётчик, если удаляется Z, затем сдвиньте
left. - После нарушения условия снова расширяйте окно справа.
Для каждого правого конца так проверяется самый короткий допустимый вариант. Более ранние начала уже длиннее; после удаления нужной Z остаётся ждать следующую. Обе границы двигаются только вперёд, каждая не более n раз. Поэтому вложенный while не делает алгоритм квадратичным: суммарное время — O(n), дополнительная память — O(1).
Есть и решение через позиции всех Z: сравнивать расстояние от первой до последней буквы в каждой группе из 270 последовательных Z. Оно тоже линейное, но хранит список позиций. Окно позволяет обойтись одними счётчиками.
Разбор на примере
Получить строку ввода (Python)
print("TT" + "Z" * 135 + "T" + "Z" * 135 + "UU")Вывод
271
| Фрагмент | Число Z | Длина |
|---|---|---|
| Вся строка | 270 | 275 |
| Без TT слева | 270 | 273 |
| Без UU справа | 270 | 271 |
| Удалена ещё одна Z | 269 | Условие нарушено |
Команда «Получить строку ввода» создаёт строку из двух 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')))
<algorithm>
<iostream>
<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
Длина включает все символы между крайними нужными буквами. Разделители внутри окна нельзя пропустить.
- Удалять по одному символу без цикла
Слева может быть много лишних символов. Цикл сжатия проверяет все допустимые уменьшения перед следующим расширением.