Δεδομένης μιας συμβολοσειράς S, πρέπει να μετρήσετε τον αριθμό των υποσυμβολοσειρών σε αυτήν που περιέχουν όλους τους χαρακτήρες αυτής της συμβολοσειράς τουλάχιστον μία φορά. Παραδείγματα: "abca" -> 3 // abc, bca, abca "aa" -> 3 // aa, a, a, "ffg" -> 2 // ffg, fg

Для решения задачи нужно найти количество подстрок, которые содержат все уникальные символы исходной строки хотя бы по одному разу.

Подход:

1. Определить множество уникальных символов исходной строки.
2. Использовать два указателя (двухуказательный слайдинг) для перебора подстрок.
3. Расширять правый указатель, пока подстрока не будет содержать все уникальные символы.
4. После этого сдвигать левый указатель, уменьшая подстроку, и считать количество подходящих подстрок.

Пример реализации на Go:

func countSubstringsWithAllChars(s string) int {
    uniqueChars := make(map[rune]struct{})
    for _, ch := range s {
        uniqueChars[ch] = struct{}{}
    }
    required := len(uniqueChars)

    windowCounts := make(map[rune]int)
    have := 0
    res := 0
    left := 0

    runes := []rune(s)

    for right, ch := range runes {
        windowCounts[ch]++
        if windowCounts[ch] == 1 { // впервые встретили этот символ в окне
            have++
        }

        for have == required {
            // Все уникальные символы есть в подстроке runes[left:right+1]
            // Все подстроки, начинающиеся с left и заканчивающиеся на right или дальше, подходят
            res += len(runes) - right

            // Сдвигаем левый указатель
            windowCounts[runes[left]]--
            if windowCounts[runes[left]] == 0 {
                have--
            }
            left++
        }
    }

    return res
}

Этот алгоритм работает за O(n), где n — длина строки, так как каждый символ обрабатывается максимум дважды.