/* Una stringa di caratteri viene data. Trovare il numero di coppie di indici i e j (i <= j), tra cui non ci sono caratteri ripetuti. Per la stringa "aba" la risposta è 5: possono essere ASCII [0, 0] ("a") [0, 1] ("ab") [1, 1] ("b") [1, 2] ("ba") [2, 2] ("a") */

Per risolvere il problema, è necessario attraversare tutte le sottostringhe della stringa e verificare che in ciascuna non ci siano caratteri ripetuti. Per farlo in modo efficiente, si può usare una finestra mobile con due puntatori e un insieme per tracciare i caratteri unici.

Esempio in Go:

func countUniqueSubstrings(s string) int {
    n := len(s)
    count := 0
    chars := make(map[byte]bool)
    j := 0

    for i := 0; i < n; i++ {
        for j < n && !chars[s[j]] {
            chars[s[j]] = true
            j++
        }
        count += j - i
        delete(chars, s[i])
    }
    return count
}

// Esempio di utilizzo:
// s := "aba"
// fmt.Println(countUniqueSubstrings(s)) // Stampa 5

Idea: estendiamo il puntatore destro j finché i caratteri sono unici, poi spostiamo il puntatore sinistro i, rimuovendo i caratteri dall'insieme. Il numero di sottostringhe uniche che iniziano con i è uguale a j - i.