Aceasta este o secvență de caractere. Găsiți numărul de perechi de indici i și j (i <= j), între care, inclusiv, nu există caractere repetate. Pentru șirul "aba" răspunsul este 5: [0, 0] ("a") [0, 1] ("ab") [1, 1] ("b") [1, 2] ("ba") [2, 2] ("a") Pentru șirul "acbb" răspunsul este ?:

Pentru șirul "acbb" trebuie să găsim numărul de perechi de indici [i, j] (i ≤ j), astfel încât substrings s[i..j] conține doar caractere unice.

Să analizăm șirul "acbb":

• [0,0] = "a" — unic
• [0,1] = "ac" — unic
• [0,2] = "acb" — unic
• [0,3] = "acbb" — repetare "b", nu se potrivește
• [1,1] = "c" — unic
• [1,2] = "cb" — unic
• [1,3] = "cbb" — repetare "b", nu se potrivește
• [2,2] = "b" — unic
• [2,3] = "bb" — repetare "b", nu se potrivește
• [3,3] = "b" — unic

În total, sunt 7 astfel de perechi.

Se poate rezolva problema folosind doi indicatori și un set pentru a urmări caracterele unice:

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
}

// Exemplu de utilizare:
// fmt.Println(countUniqueSubstrings("acbb")) // Va afișa 7

Acest algoritm funcționează în O(n), unde n este lungimea șirului.