01 Что мы уже умеем
Мы научились решать задачи с простыми объектами — один символ или фиксированная пара:
| Задача |
Метод |
| Не более K букв X → max |
Шаблон 1 (скользящее окно) |
| Не менее K букв X → min |
Шаблон 2 (скользящее окно) |
| Ровно K букв X → max |
Шаблон 3 (позиции) |
| Ровно K букв X → кол-во |
Шаблон 4 (atMost−atMost) |
⚠️ А что если объект сложнее? Найти минимальную подстроку, содержащую не менее K слов с буквой Q.
Слово — это непустая последовательность букв между точками.
02 Идея: разделяй и властвуй
Этап 1 · Найти объекты
Находим все слова с Q и запоминаем их позиции (начало и конец).
Инструмент: regex или ручной парсинг.
Этап 2 · Применить шаблон
Когда есть список позиций объектов, задача сводится к знакомой:
Шаблон 2: «не менее K объектов, ищем минимум».
✅ Универсальный принцип Любой сложный объект (слово с Q, пара символов, подстрока по паттерну) → сначала найди все вхождения, потом применяй шаблон скользящего окна к списку найденных объектов.
03 Пошаговый разбор
Строка AB.QX.CD.QR.EF.QZ.GH, символ Q, не менее K=2 слов с Q.
Интерактивный разбор · два этапа
Исходная строка
Найденные объекты (слова с Q)
Нажмите «Шаг» или «Авто»
04 Как разбить на слова (подсказки)
Задача: из строки вида AB.QX.CD.QR.EF извлечь все слова, содержащие нужную букву, и запомнить их позиции. Вот несколько способов:
Способ 1: str.split()
Разбиваем строку по разделителю (точке) методом split('.'). Получаем список слов. Дальше перебираем слова, проверяем наличие нужной буквы оператором in и вычисляем позиции каждого слова в исходной строке, отслеживая смещение.
💡 Подсказка по позициям При split нужно самостоятельно вычислять позиции: после каждого слова прибавлять его длину + 1 (за разделитель).
Способ 2: re.finditer()
Регулярное выражение позволяет найти слова с нужной буквой за один проход. Метод finditer возвращает объекты совпадений, у каждого из которых есть .start() и .end() — готовые позиции.
💡 Какой паттерн использовать? Нужно описать «непустая последовательность символов, не являющихся точкой, в которой есть буква Q». Подумайте: как описать «любые символы, кроме точки» с помощью символьного класса [^.], и как потребовать, чтобы среди них была буква Q?
Способ 3: ручной посимвольный обход
Идём по строке символ за символом. Встретив разделитель — завершаем текущее слово. Если в процессе набора слова встретили целевую букву — помечаем слово как подходящее. Запоминаем начальную и конечную позиции.
⚠️ Этап 2 — применить шаблон Когда список позиций слов с Q собран, задача сводится к знакомой: «не менее K объектов → ищем минимум». Это Шаблон 2, но вместо отдельных символов — целые слова с известными границами. Перебираем все группы из K подряд идущих объектов и для каждой считаем длину покрытия от начала первого до конца последнего.
🎯 Попробуй сам! Реализуй оба этапа самостоятельно. Визуализатор ниже поможет проверить, правильно ли работает твоё решение.
05 Песочница
Песочница · своя задача
Строка
Найденные объекты
Нажмите «Применить», затем «Шаг»
💡 Нажмите на тест — подставится автоматически
06 Тесты
Попробуй · тестирование
AB.QX.CD.QR.EF.QZ.GHQ≥2Ответ:?
QA.BB.QC.DD.QEQ≥3Ответ:?
AA.BB.CCQ≥1Ответ:?
QQ.Q.QQQ≥2Ответ:?