Модуль: Скользящее окно и два указателя

Шаблон 2 — "НЕ МЕНЕЕ K раз", ищем МИНИМУМ

Задача-пример

Найти минимальную подстроку, где буква X встречается не менее 2 раз.

Строка: A B X A X X A B

Принцип

1. Двигаем right вправо, пока условие не выполнено
2. Когда условие выполнено (X >= 2) — обновляем минимум и сужаем
3. Обновляем ответ внутри while, пока условие ещё выполняется

Пошаговый разбор

Строка: A B X A X X A B
        0 1 2 3 4 5 6 7

Начало: left=0, count_x=0, min_len=∞

Шаги 1-3: right=0,1,2

        A B X A X X A B
        ↑   ↑
        L   R
        
count_x = 1 (<2) — условие НЕ выполнено, просто идём дальше

Шаг 4: right=3, символ 'A'

        A B X A X X A B
        ↑     ↑
        L     R
        
count_x = 1 (<2) — условие НЕ выполнено

Шаг 5: right=4, символ 'X'

        A B X A X X A B
        ↑       ↑
        L       R
        
count_x = 2 (≥2 ) — условие ВЫПОЛНЕНО!

Входим в while, обновляем ВНУТРИ:
  min_len = min(∞, 4-0+1) = 5
  left=0: 'A' — сдвигаем, count_x=2
  
  min_len = min(5, 4-1+1) = 4
  left=1: 'B' — сдвигаем, count_x=2
  
  min_len = min(4, 4-2+1) = 3
  left=2: 'X' — сдвигаем, count_x=1 (<2) — выходим из while

        A B X A X X A B
              ↑   ↑
              L   R

Шаг 6: right=5, символ 'X'

        A B X A X X A B
              ↑     ↑
              L     R
        
count_x = 2 (≥2 ✓) — условие ВЫПОЛНЕНО!

Входим в while:
  min_len = min(3, 5-3+1) = 3
  left=3: 'A' — сдвигаем, count_x=2
  
  min_len = min(3, 5-4+1) = 2  ← НОВЫЙ МИНИМУМ!
  left=4: 'X' — сдвигаем, count_x=1 (<2) — выходим

        A B X A X X A B
                ↑   ↑
                L   R

Шаги 7-8: right=6,7

count_x остаётся 1 (<2) — условие не выполнено, while не срабатывает

Ответ: 2

Минимальная подстрока: X X (позиции 4-5)

Код

def min_at_least_k(s, k):
    left = 0
    count_x = 0
    min_len = float('inf')
    
    for right in range(len(s)):
        if s[right] == 'X':
            count_x += 1
        
        while count_x >= k:         # пока выполнено
            min_len = min(min_len, right - left + 1)  # ВНУТРИ while
            if s[left] == 'X':
                count_x -= 1
            left += 1
    
    return min_len

Ключевое правило Шаблона 2

┌─────────────────────────────────────────────┐
│  while count >= k   ← сужаем ПОКА выполнено │
│  обновляем ВНУТРИ while ← ловим минимум     │
└─────────────────────────────────────────────┘