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)📌 Чем окно проще двойного указателя В двойном указателе |