sliding-window

Siljuvchi oyna — massivda ketma-ket oraliqni ikki ko‘rsatkich (left, right) bilan ushlab, uni o‘ngga suramiz. Har element oynaga bir marta kiradi va bir marta chiqadi — jami O(n).

Belgilangan uzunlikdagi oyna

window = sum(a[:k])
best = window
for i in range(k, len(a)):
    window += a[i] - a[i - k]     # yangisi kiradi, eskisi chiqadi
    best = max(best, window)

O‘zgaruvchan oyna: shartga mos eng uzun oraliq

left = total = best = 0
for right, x in enumerate(a):
    total += x
    while total > limit:          # shart buzildi — chapdan qisqartiramiz
        total -= a[left]
        left += 1
    best = max(best, right - left + 1)

Takrorlanmas belgili eng uzun qism satr kabi masalalarda oyna ichidagi belgilar dict/set da saqlanadi.