Il s'agit d'une chaîne de caractères. Trouvez le nombre de paires d'indices i et j (i <= j), entre lesquelles, inclus, il n'y a pas de caractères répétés. Pour la chaîne "aba", la réponse est 5 : [0, 0] ("a") [0, 1] ("ab") [1, 1] ("b") [1, 2] ("ba") [2, 2] ("a") Pour la chaîne "acbb", la réponse est ?:

Pour la chaîne "acbb", il faut trouver le nombre de paires d’indices [i, j] (i ≤ j), telles que la sous-chaîne s[i..j] ne contient que des caractères uniques.

Analysons la chaîne "acbb" :

• [0,0] = "a" — unique
• [0,1] = "ac" — unique
• [0,2] = "acb" — unique
• [0,3] = "acbb" — répétition "b", non valide
• [1,1] = "c" — unique
• [1,2] = "cb" — unique
• [1,3] = "cbb" — répétition "b", non valide
• [2,2] = "b" — unique
• [2,3] = "bb" — répétition "b", non valide
• [3,3] = "b" — unique

Au total, 7 paires.

On peut résoudre ce problème en utilisant deux pointeurs et un ensemble pour suivre les caractères uniques :

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
}

// Exemple d’utilisation :
// fmt.Println(countUniqueSubstrings("acbb")) // Affiche 7

Cet algorithme fonctionne en O(n), où n est la longueur de la chaîne.