sirag

Algoritmul, pas cu pas

Imaginează-ți că tai o secvență în bucăți lipite, ca pe un șirag de mărgele. O tăiere e echilibrată dacă toate bucățile au exact același număr de litere distincte — și ai făcut cel puțin o tăietură (deci cel puțin două bucăți). Trebuie să numeri câte astfel de tăieri are fiecare secvență contiguă a șirului și să aduni totul.

Cheia e că „numărul comun de litere distincte" $d$ poate fi orice valoare de la $1$ la $26$. Deci fixăm pe rând fiecare $d$ și numărăm doar tăierile în care fiecare bloc are exact $d$ litere distincte; la final adunăm peste toți $d$.