Ez egy karakterlánc. Keresse meg az i és j indexpárok számát (i <= j), amelyek között, beleértve, nincsenek ismétlődő karakterek. A "aba" karakterlánc esetén a válasz 5: [0, 0] ("a") [0, 1] ("ab") [1, 1] ("b") [1, 2] ("ba") [2, 2] ("a") Az "acbb" karakterlánc esetén a válasz ?:

Az "acbb" sztringhez meg kell találni az [i, j] indexpárokat (i ≤ j), amelyek esetén az s[i..j] részsztring csak egyedi karaktereket tartalmaz.

Elemzzük az "acbb" sztringet:

• [0,0] = "a" — egyedi
• [0,1] = "ac" — egyedi
• [0,2] = "acb" — egyedi
• [0,3] = "acbb" — ismétlődés "b", nem megfelelő
• [1,1] = "c" — egyedi
• [1,2] = "cb" — egyedi
• [1,3] = "cbb" — ismétlődés "b", nem megfelelő
• [2,2] = "b" — egyedi
• [2,3] = "bb" — ismétlődés "b", nem megfelelő
• [3,3] = "b" — egyedi

Összesen 7 ilyen pár van.

A problémát két mutató és egy halmaz segítségével lehet megoldani, amely nyomon követi az egyedi karaktereket:

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
}

// Példa használat:
// fmt.Println(countUniqueSubstrings("acbb")) // 7-et ír ki

Ez az algoritmus O(n) időben működik, ahol n a sztring hossza.