Вспомним, что мы уже умеем
Мы научились решать задачи, где нужно найти подстроку с условием на символы или пары символов:
- «не более K букв X» → скользящее окно
- «ровно K пар CD» → перебор по позициям пар
- «ровно 1 X и ровно 1 Y» → отслеживание последних позиций
Во всех этих задачах объект поиска простой — один символ или фиксированная пара.
А что если объект сложнее?
Рассмотрим задачу:
Найдите минимальную длину подстроки, содержащую не менее K слов, содержащих букву Q (слова могут отделяться пробелом или другим условным символом, например точкой).
Здесь
объект поиска — это «слово, содержащее Q».
Что такое слово? Непустая последовательность букв между точками: .ABC., .Q., .XQYZ.
Вопрос: Как найти все такие слова?
Идея: разделяй и властвуй
Можно разбить задачу на два этапа:
Этап 1: Найти все «сложные объекты»
Сначала находим все слова, содержащие Q, и запоминаем их позиции (начало и конец).
Подсказка: Для поиска сложных паттернов удобно использовать регулярные выражения.
(если вы еще не познакомились с регулярными выражениями, то очень советуем это сделать. У нас есть целый
раздел учебника, посвященный этой теме)
Этап 2: Применить знакомую технику
Когда у нас есть список позиций объектов, задача сводится к уже знакомой:
Найти минимальную подстроку, содержащую не менее K объектов.
А это мы уже умеем! Какой шаблон здесь подходит?