Ctrl K

Одинокие буквы во всех подстроках

Сложная
Назовём букву подстроки одинокой, если она встречается в этой подстроке ровно один раз. Например, в "BANANA" одинока только B, а в "ANT" одиноки все три буквы. Дана строка word. Для каждой её непустой подстроки посчитайте число одиноких букв и верните сумму этих чисел. Подстроки, совпадающие по тексту, но стоящие на разных позициях, считаются отдельно. Перебор всех подстрок слишком медленный — попробуйте уложиться в линейное время.
Пример 1
word="AB" → 4

Подстроки: "A" (1), "B" (1), "AB" (2). Сумма — 4.

Пример 2
word="AAB" → 6

"A", "A", "B" дают по 1, "AA" — 0 (буква повторяется), "AB" — 2, "AAB" — 1 (одиночка только B). Итого 6.

Пример 3
word="ZZZ" → 3
Ограничения
  • 1 ≤ len(word) ≤ 10⁵
  • word состоит из заглавных латинских букв
  • Ответ помещается в 32-битное целое
Встречал эту задачу на настоящем собесе?
Решили0
Пробовали0
Отправок0
Принято—
Темы
Похожие задачиВсе способы расставить пробелы СложнаяСумма разнообразия подстрок СложнаяДлина разросшегося слова СложнаяУравнять частоты букв СложнаяРазбиение на слова из словаря Средняя
загружаем Python…
Вход
word="AB"
Ожидается
4

«Запустить» — первые 3 теста у тебя в браузере, «Отправить» — все 160 тестов на сервере, включая скрытые.