Това е низ от символи. Намерете броя на двойките индекси i и j (i <= j), между които, включително, няма повтарящи се символи. За низа "aba" отговорът е 5: [0, 0] ("a") [0, 1] ("ab") [1, 1] ("b") [1, 2] ("ba") [2, 2] ("a") За низа "acbb" отговорът е ?:

За низа "acbb" трябва да намерим броя на двойките индекси [i, j] (i ≤ j), такива че поднизът s[i..j] съдържа само уникални символи.

Разгледаме низа "acbb":

• [0,0] = "a" — уникално
• [0,1] = "ac" — уникално
• [0,2] = "acb" — уникално
• [0,3] = "acbb" — повторение "b", не е подходящо
• [1,1] = "c" — уникално
• [1,2] = "cb" — уникално
• [1,3] = "cbb" — повторение "b", не е подходящо
• [2,2] = "b" — уникално
• [2,3] = "bb" — повторение "b", не е подходящо
• [3,3] = "b" — уникално

Общо има 7 такива двойки.

Може да решите задачата с помощта на два показалеца и множество за проследяване на уникалните символи:

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
}

// Пример за използване:
// fmt.Println(countUniqueSubstrings("acbb")) // Ще изведе 7

Този алгоритъм работи с времева сложност O(n), където n е дължината на низа.