Почти чётные подстроки

Средняя

Назовём строку *почти чётной*, если в ней не больше одной буквы встречается нечётное число раз. Например, "ddefe" и "gg" почти чётные, а "de" — нет. Дана строка text из букв от a до j. Посчитайте, сколько её непустых подстрок (непрерывных кусков) почти чётные. Одинаковые подстроки на разных позициях считаются отдельно.

Пример 1

text="cac" → 4

Подходят «c», «a», «c» и вся строка «cac» (в ней нечётно только «a»). «ca» и «ac» не подходят — там обе буквы встречаются по разу.

Пример 2

text="bbb" → 6

Все шесть подстрок состоят из одной буквы, так что нечётной может быть только она.

Пример 3

text="adf" → 3

Ограничения

1 ≤ len(text) ≤ 10⁵
text состоит из строчных латинских букв от a до j

Встречал эту задачу на настоящем собесе?

Решили0

Пробовали0

Отправок0

Принято—

Темы

Bit Manipulation Hash Table String Prefix Sum

Вход

text="cac"

Ожидается

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