Дана строка 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 — длина строки, так как каждый символ обрабатывается максимум дважды.