6 Метод 3 — плавающее окно

Метод 3 — плавающее окно

Когда удобен: это двойной указатель, но проще — оба края окна [left, right] движутся только вперёд. right расширяет окно на каждом шаге, а left подтягивается, только когда внутри окна нарушилось условие. Отвечает на вопросы вида «самая длинная цепочка, где выполнено такое-то свойство про весь фрагмент».

Например, «самая длинная цепочка, в которой не более двух различных букв»:

from collections import Counter
s = open("24.txt").readline().strip()
cnt = Counter()
left = 0
mx = 0
for right in range(len(s)):
    cnt[s[right]] += 1                   # добавили правый символ в окно
    while len(cnt) > 2:                  # нарушено: различных букв больше двух
        cnt[s[left]] -= 1                # сжимаем окно слева
        if cnt[s[left]] == 0:
            del cnt[s[left]]
        left += 1
    mx = max(mx, right - left + 1)       # длина текущего окна
print(mx)

📌 Чем окно проще двойного указателя

В двойном указателе i иногда «прыгает» сразу к j. В плавающем окне оба края ползут по одному шагу и никогда не откатываются назад. Расширяем справа — при нарушении подтягиваем слева. За это его и любят: логика линейная и её трудно сломать.