Questa è una stringa di caratteri. Trova il numero di coppie di indici i e j (i <= j), tra cui, ci sono caratteri non ripetuti. Per la stringa "aba" la risposta è 5: [0, 0] ("a") [0, 1] ("ab") [1, 1] ("b") [1, 2] ("ba") [2, 2] ("a") Per la stringa "acbb" la risposta è ?:

Per la stringa "acbb" è necessario trovare il numero di coppie di indici [i, j] (i ≤ j), tali che la sottostringa s[i..j] contenga solo caratteri unici.

Analizziamo la stringa "acbb":

• [0,0] = "a" — unico
• [0,1] = "ac" — unico
• [0,2] = "acb" — unico
• [0,3] = "acbb" — ripetizione "b", non valido
• [1,1] = "c" — unico
• [1,2] = "cb" — unico
• [1,3] = "cbb" — ripetizione "b", non valido
• [2,2] = "b" — unico
• [2,3] = "bb" — ripetizione "b", non valido
• [3,3] = "b" — unico

In totale, ci sono 7 coppie.

Puoi risolvere il problema usando due puntatori e un insieme per tracciare i caratteri unici:

func countUniqueSubstrings(s string) int {
    seen := make(map[rune]bool)
    count := 0
    left := 0
    for right, ch := range s {
        for seen[ch] {
            delete(seen, rune(s[left]))
            left++
        }
        seen[ch] = true
        count += right - left + 1
    }
    return count
}

// Esempio di utilizzo:
// fmt.Println(countUniqueSubstrings("acbb")) // Stampa 7

Questo algoritmo funziona in O(n), dove n è la lunghezza della stringa.