Дана строка. Посчитайте, сколько её подстрок содержат все различные символы
исходной строки хотя бы по одному разу. Подстроки считаются по позициям:
одинаковые по содержимому, но стоящие в разных местах, — разные. (Обобщение
LeetCode 1358 Number of Substrings Containing All Three Characters на
произвольный алфавит.)
// CountWithAll возвращает число подстрок s (по позициям), содержащих
// каждый символ, встречающийся в s.
func CountWithAll(s string) int
Примеры
"xxyz" → 2 // "xxyz", "xyz"
"yy" → 3 // "y", "y", "yy"
"xyz" → 1
"xyzxyz" → 10
"" → 0
Ограничения
0 ≤ len(s) ≤ 10⁶. Строка в UTF-8, символ — руна.- Ответ может достигать n(n+1)/2 ≈ 5·10¹¹ — нужен 64-битный
int.
- Ожидается O(n) в среднем, независимо от числа различных символов.
Разбор и эталонное решение — после своей попытки: на собеседовании подсказок не будет.
Сначала попробуй сам — подсказки не дают готовый ответ.