Скользящее окно

Как найти самый длинный фрагмент, в котором не больше двух букв A? Цепочка здесь не поможет: одна лишняя A не обнуляет всё, что было до неё.

Хранить две границы фрагмента — окна. Правая идёт по строке по одному символу. Когда букв A стало больше двух, левая сдвигается вправо, пока лишняя A не уйдёт из окна. Количество A в окне хранится в счётчике: правая граница добавляет символ, левая убирает.

s = 'BABAACB'left = 0count = 0best = 0for right in range(len(s)):    if s[right] == 'A':        count += 1    while count > 2:        if s[left] == 'A':            count -= 1        left += 1    best = max(best, right - left + 1) print(best)

Пройди строку BABAACB по шагам. Самый важный момент — третья A на позиции 4: окно BABAA плохое. Убираем B — в ABAA всё ещё три A. Убираем A — в BAA их две. Поэтому нужен while, а не if: иногда убрать надо несколько символов.

Ответ — 5, окно BAACB. Вложенный цикл не делает программу медленной: left никогда не идёт назад, поэтому за весь проход он сдвинется не больше len(s) раз. Миллион символов — около двух миллионов шагов.

В условии: «буква T встречается ровно 100 раз». Что поменять в окне?

Окно то же — левая граница двигается, пока букв больше K. А ответ обновляется, только когда их ровно K. Меньше K — фрагмент ещё не подходит, а сужение окна букв не прибавит.

s = 'BABAACB'left = 0count = 0best = 0for right in range(len(s)):    if s[right] == 'A':        count += 1    while count > 2:        if s[left] == 'A':            count -= 1        left += 1    if count == 2:        best = max(best, right - left + 1) print(best)

На экзамене K = 100, а файл — миллион символов: программа та же, меняется только число. Если в строке меньше K нужных букв, best останется 0 — подходящего фрагмента нет.

Нужен самый длинный фрагмент, где буквы идут в алфавитном порядке и гласных не больше одной. Как совместить два условия?

Каждое условие — своим приёмом. Нарушение порядка — условие на соседей: окно начинается заново с текущей буквы. Лишняя гласная — ограничение на количество: левая граница догоняет.

s = 'AEKZIOPSW'vowels = 'AEIOUY'left = 0count = 0best = 0for right in range(len(s)):    if right > 0 and s[right] < s[right - 1]:        left = right        count = 0    if s[right] in vowels:        count += 1    while count > 1:        if s[left] in vowels:            count -= 1        left += 1    best = max(best, right - left + 1) print(best)

Ответ — 4, фрагмент OPSW. EKZ тоже по алфавиту, но короче, а после Z порядок рушится: I меньше Z.

Если ограничение на каждую из нескольких букв — «J, K, X и Z не больше 6 раз каждая», — счётчики держат в словаре, а окно сжимают, пока превышен счётчик только что добавленной буквы.

Ограничение бывает на пары: «пара гласная + согласная встречается не больше 130 раз». Когда пара входит в окно и когда уходит?

Пара считается, только когда лежит в окне целиком. Она входит, когда правая граница добавляет её второй символ, и уходит, когда левая проходит её первый. Пары могут перекрываться: в TTT две пары TT. Пара, которая кончается на right, — это срез s[right - 1:right + 1], а пара, которая начинается на left, — s[left:left + 2].

s = 'TTATTTB'left = 0pairs = 0best = 0for right in range(len(s)):    if right > 0 and s[right - 1:right + 1] == 'TT':        pairs += 1    while pairs > 1:        if s[left:left + 2] == 'TT':            pairs -= 1        left += 1    best = max(best, right - left + 1) print(best)

Пройди по шагам: на позиции 5 появляется пара TT, которая перекрывается с парой 3–4. Пар стало две, и левая граница уходит за T на позиции 3.

Окна TTAT и TATT содержат по одной целой паре — ответ 4. Для пары «гласная + согласная» меняется только проверка: s[right - 1] in vowels and s[right] not in vowels.

• Окноright идёт вперёд, left догоняет по while
• Не более Kсжимать, пока count > K
• Ровно Kответ — только при count == K
• Порядок и количествонарушен порядок — left = right; лишняя буква — while
• Парывходит со вторым символом, уходит с первым
• Скоростьleft не идёт назад: O(n)