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

Оба метода работают с подстроками и используют два указателя left и right:

Строка:  A B X A X X A B A
         ↑       ↑
        left   right
         └───────┘
         окно (подстрока)

Шаблон 1 — "НЕ БОЛЕЕ K раз", ищем МАКСИМУМ

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

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

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

Принцип

1. Двигаем right вправо, добавляя символы в окно
2. Если условие нарушено (X больше 2) — двигаем left вправо
3. После исправления окно всегда валидно → обновляем максимум

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

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

Начало: left=0, count_x=0, max_len=0

Шаг 1: right=0, символ 'A'

        A B X A X X A B
        ↑
        L,R
        
count_x = 0 (≤2)
max_len = max(0, 0-0+1) = 1

Шаг 2: right=1, символ 'B'

        A B X A X X A B
        ↑ ↑
        L R
        
count_x = 0 (≤2)
max_len = max(1, 1-0+1) = 2

Шаг 3: right=2, символ 'X'

        A B X A X X A B
        ↑   ↑
        L   R
        
count_x = 1 (≤2)
max_len = max(2, 2-0+1) = 3

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

        A B X A X X A B
        ↑     ↑
        L     R
        
count_x = 1 (≤2)
max_len = max(3, 3-0+1) = 4

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

        A B X A X X A B
        ↑       ↑
        L       R
        
count_x = 2 (≤2)
max_len = max(4, 4-0+1) = 5

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

        A B X A X X A B
        ↑         ↑
        L         R
        
count_x = 3 (>2 ✗) — условие НАРУШЕНО!

Сужаем окно, двигаем left:
  left=0: 'A' — не X, просто сдвигаем
  left=1: 'B' — не X, просто сдвигаем  
  left=2: 'X' — это X! count_x = 2
  left=3 (остановились, т.к. count_x ≤ 2)

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

count_x = 2 (≤2 ✓)
max_len = max(5, 5-3+1) = 5

Шаг 7: right=6, символ 'A'

        A B X A X X A B
              ↑       ↑
              L       R
        
count_x = 2 (≤2 ✓)
max_len = max(5, 6-3+1) = 5

Шаг 8: right=7, символ 'B'

        A B X A X X A B
              ↑         ↑
              L         R
        
count_x = 2 (≤2 ✓)
max_len = max(5, 7-3+1) = 5

Ответ: 5

Максимальная подстрока: A X X A B (позиции 3-7) или A B X A X (позиции 0-4)

Код

def max_at_most_k(s, k):
    left = 0
    count_x = 0
    max_len = 0
    
    for right in range(len(s)):
        if s[right] == 'X':
            count_x += 1
        
        while count_x > k:          # пока нарушено
            if s[left] == 'X':
                count_x -= 1
            left += 1
        
        max_len = max(max_len, right - left + 1)  # ПОСЛЕ while
    
    return max_len

Ключевое правило Шаблона 1
┌────────────────────────────────────────────┐
│  while count > k    ← сужаем ПОКА нарушено │
│  обновляем ПОСЛЕ while ← окно уже валидно  │
└────────────────────────────────────────────┘