Dies ist eine Zeichenkette. Finden Sie die Anzahl der Indexpaare i und j (i <= j), zwischen denen einschließlich keine wiederholten Zeichen vorhanden sind. Für die Zeichenkette "aba" ist die Antwort 5: [0, 0] ("a") [0, 1] ("ab") [1, 1] ("b") [1, 2] ("ba") [2, 2] ("a") Für die Zeichenkette "acbb" ist die Antwort ?:

Für die Zeichenkette "acbb" muss die Anzahl der Indexpaare [i, j] (i ≤ j) gefunden werden, bei denen die Teilzeichenkette s[i..j] nur aus einzigartigen Zeichen besteht.

Betrachten wir die Zeichenkette "acbb":

• [0,0] = "a" — einzigartig
• [0,1] = "ac" — einzigartig
• [0,2] = "acb" — einzigartig
• [0,3] = "acbb" — Wiederholung "b", nicht geeignet
• [1,1] = "c" — einzigartig
• [1,2] = "cb" — einzigartig
• [1,3] = "cbb" — Wiederholung "b", nicht geeignet
• [2,2] = "b" — einzigartig
• [2,3] = "bb" — Wiederholung "b", nicht geeignet
• [3,3] = "b" — einzigartig

Insgesamt 7 solcher Paare.

Dieses Problem kann mit zwei Zeigern und einer Menge zur Verfolgung der einzigartigen Zeichen gelöst werden:

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
}

// Beispiel:
// fmt.Println(countUniqueSubstrings("acbb")) // Gibt 7 aus

Dieser Algorithmus läuft in O(n), wobei n die Länge der Zeichenkette ist.