Задание №24. Короткий конспект
Границы окна, целые вхождения, выбор экстремума и проверка единиц ответа.
В задании №24 из строки выбирается непрерывный фрагмент с нужными свойствами. До поиска определяются цель — минимум или максимум — и единица ответа: символы либо целые блоки.
Границы и счётчик
Индексы начинаются с нуля. Границы l,r включены; фрагмент — s[l:r+1], длина — r-l+1. Правая граница среза Python не включается, поэтому используется r+1.
Целое вхождение учитывается только внутри окна. При расширении добавляются вхождения, закончившиеся на новом символе. Перед удалением левого символа вычитаются включённые вхождения, начинающиеся на нём. Остальная часть счётчика не меняется.
Выбор границ
Пусть K — требуемое количество, c — текущий счётчик одной квоты.
| Цель | Действие |
|---|---|
| Максимум, c\le K | Удалить избыток слева; учесть длину. |
| Максимум, c=K | Удалить избыток; учесть длину только при равенстве. |
| Минимум, c\ge K | Сжимать допустимое окно, сохраняя кандидата перед нарушением. |
Для одной положительной квоты кратчайшее окно с не менее чем K вхождениями содержит ровно K. Если первое и последнее начинаются на p,q, а длина шаблона равна m, его длина — q-p+m. Несколько требований проверяются одновременно; одного счётчика недостаточно.
Дополнительные условия
- Заданные начало и конец проверяются вместе с квотами. Запрещённый шаблон с началом p требует l\ge p+1; разрешённый суффикс сохраняется.
- Целые пары не перекрываются. Проверяются оба выравнивания начала; число пар равно (r-l+1)/2.
- В основании 14 допустимы
0123456789ABCD, чётные последние цифры —02468AC. Ведущие нули не увеличивают значащую длину. - Число в выражении —
0либо запись с ненулевой первой цифрой. Между числами ровно одна операция; начало и конец — цифры.07и два знака подряд недопустимы. Значение выражения вычислять не требуется.
Возможные ловушки
Пропуск последнего символа теряет окно у конца файла. Подсчёт отдельных букв вместо пар меняет квоту; str.count пропускает перекрывающиеся вхождения. В условии с ровно 190 BC ↗ замена равенства верхним ограничением допускает недостаточное количество. В запрете XZZY ↗ удаление всего шаблона может сократить максимум. В итоговой проверке сверяются границы, все дополнительные условия и единицы ответа.