Cos'è la tecnica della finestra scorrevole (sliding-window)?

Question

Accepted Answer

La tecnica **sliding-window** mantiene un intervallo contiguo (finestra) su un array o stringa e la fa scorrere invece di ricalcolare da zero, risolvendo molti problemi di subarray/substring in **O(n)**.

## L'idea

Espandi la finestra spostando il bordo destro; riducila spostando il bordo sinistro quando un vincolo è violato. Riutilizza il calcolo precedente invece di riscansionare.

## Esempio: somma massima di qualsiasi finestra di dimensione k

```python
def max_window_sum(arr, k):
    window = sum(arr[:k])       # sum of first window
    best = window
    for i in range(k, len(arr)):
        window += arr[i] - arr[i - k]  # add new, drop old
        best = max(best, window)
    return best

max_window_sum([2, 1, 5, 1, 3, 2], 3)  # -> 9 (5+1+3)
```

## Complessità

- **Tempo:** O(n) — ogni elemento entra e esce dalla finestra una sola volta.
- **Spazio:** O(1) per finestre fisse, O(k) quando si tiene traccia dei contenuti.

## Quando usarla / insidie

Usala per problemi "longest/shortest/max subarray con proprietà X". Per finestre **variabili**, avanza il puntatore sinistro per ripristinare il vincolo. Fai attenzione agli errori off-by-one quando aggiungi/rimuovi elementi al bordo.

## Perché è importante

La finestra scorrevole elimina il lavoro ridondante, trasformando il ricalcolo O(n·k) in un singolo passaggio.

È il pattern ideale per problemi di substring e subarray che appaiono costantemente nei colloqui.

L'intuizione — riutilizzare il risultato precedente invece di ricalcolare — si generalizza ai dati in streaming e in tempo reale.