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

Шаблон 4 — "РОВНО K раз", считаем КОЛИЧЕСТВО подстрок

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

Сколько подстрок содержат букву X ровно 2 раза?

Строка: A X X A

Принцип

Количество(ровно K) = Количество(не более K) − Количество(не более K-1)

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

Сначала посчитаем подстроки с не более 2 букв X:

Строка: A X X A
        0 1 2 3

Для "не более K" считаем: на каждом шаге все подстроки, заканчивающиеся в right.

right=0: окно [0,0]="A", подстроки: "A" → +1
right=1: окно [0,1]="AX", подстроки: "AX", "X" → +2
right=2: окно [0,2]="AXX", подстроки: "AXX", "XX", "X" → +3
right=3: окно [0,3]="AXXA", подстроки: "AXXA", "XXA", "XA", "A" → +4

Итого "не более 2": 1 + 2 + 3 + 4 = 10

Теперь посчитаем подстроки с не более 1 буквы X:

right=0: окно [0,0]="A" → +1
right=1: окно [0,1]="AX" → +2
right=2: count=2 > 1, сужаем до [2,2]="X" → +1
right=3: окно [2,3]="XA" → +2

Итого "не более 1": 1 + 2 + 1 + 2 = 6

Ответ

Ровно 2 = (не более 2) − (не более 1) = 10 − 6 = 4

Проверим: подстроки с ровно 2 буквами X:

• "AXX" (позиции 0-2)
• "XX" (позиции 1-2)
• "XXA" (позиции 1-3)
• "AXXA" (позиции 0-3)

Код

def count_exactly_k(s, k):
    def count_at_most(k):
        if k < 0:
            return 0
        left = 0
        count_x = 0
        result = 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
            
            result += right - left + 1  # все подстроки [left..right], [left+1..right], ...
        
        return result
    
    return count_at_most(k) - count_at_most(k - 1)

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

┌──────────────────────────────────────────────────┐
│  exactly(K) = atMost(K) − atMost(K − 1)          │
│  На каждом шаге: result += right − left + 1      │
└──────────────────────────────────────────────────┘

• Может появиться в будущем
• Помогает глубже понять связь между "не более K" и "ровно K"