Étant donné une chaîne S, il faut compter le nombre de sous-chaînes dans cette chaîne qui contiennent tous les caractères de cette chaîne au moins une fois. Exemples : "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 — длина строки, так как каждый символ обрабатывается максимум дважды.