Dit is een tekenreeks. Vind het aantal paren indices i en j (i <= j), tussen welke, inclusief, geen herhaalde tekens zijn. Voor de tekenreeks "aba" is het antwoord 5: [0, 0] ("a") [0, 1] ("ab") [1, 1] ("b") [1, 2] ("ba") [2, 2] ("a") Voor de tekenreeks "acbb" is het antwoord ?:

Voor de string "acbb" moet het aantal paren indices [i, j] (i ≤ j) worden gevonden, zodanig dat de substring s[i..j] alleen unieke tekens bevat.

Laten we de string "acbb" analyseren:

• [0,0] = "a" — uniek
• [0,1] = "ac" — uniek
• [0,2] = "acb" — uniek
• [0,3] = "acbb" — herhaling "b", niet geschikt
• [1,1] = "c" — uniek
• [1,2] = "cb" — uniek
• [1,3] = "cbb" — herhaling "b", niet geschikt
• [2,2] = "b" — uniek
• [2,3] = "bb" — herhaling "b", niet geschikt
• [3,3] = "b" — uniek

In totaal zijn er 7 zulke paren.

Dit probleem kan worden opgelost met behulp van twee pointers en een set om de unieke tekens bij te houden:

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
}

// Voorbeeld van gebruik:
// fmt.Println(countUniqueSubstrings("acbb")) // Drukt 7 af

Dit algoritme werkt in O(n), waarbij n de lengte van de string is.