Beschreiben Sie den Algorithmus zur Zählung von Teilstrings mit allen einzigartigen Zeichen

Для подсчёта количества подстрок с уникальными символами обычно используют алгоритм "скользящего окна" (sliding window). Идея в том, чтобы поддерживать окно, в котором все символы уникальны, и перемещать его по строке, подсчитывая количество таких подстрок.

Основные шаги:

1. Использовать два указателя — left и right, которые определяют границы окна.
2. Использовать структуру данных (например, мапу или массив) для отслеживания встреченных символов и их количества.
3. Расширять окно вправо, добавляя символы, пока все они уникальны.
4. Если встречается повторяющийся символ, сдвигать левый указатель вправо, уменьшая счетчики символов, пока повтор не исчезнет.
5. На каждом шаге можно подсчитывать количество уникальных подстрок, например, добавляя right - left + 1.

Пример на Go:

func countUniqueSubstrings(s string) int {
    freq := make(map[rune]int)
    left, count := 0, 0
    for right, ch := range s {
        freq[ch]++
        for freq[ch] > 1 {
            freq[rune(s[left])]--
            left++
        }
        count += right - left + 1
    }
    return count
}

Здесь count — общее количество подстрок с уникальными символами.