Количество подстрок с частотой не более одного символа как Odd

Для заданной строки S из N символов задача состоит в том, чтобы вычислить общее количество непустых подстрок, в которых не более одного символа встречается нечетное количество раз.

Пример :

Input: S = “aba”
Output: 4
Explanation: The valid substrings are “a”, “b”, “a”, and “aba”. Therefore, the total number of required substrings are 4.

Input: “aabb”
Output: 9
Explanation: The valid substrings are “a”, “aa”, “aab”, “aabb”, “a”, “abb”, “b”, “bb”, and “b”.

Подход : Вышеупомянутая проблема может быть решена с помощью Bit Masking с использованием HashMaps. Выполните следующие шаги, чтобы решить проблему:

• Четность частоты каждого символа может храниться в битовой маске , где i ^-й символ представлен 2 ⁱ . Изначально значение маски = 0 .
• Создайте неупорядоченную карту visible , в которой хранится частота появления каждой битовой маски. Изначально значение visible[0] = 1 .
• Создайте переменную cnt , в которой хранится количество допустимых подстрок. Изначально значение cnt = 0 .
• Выполните итерацию для каждого i в диапазоне [0, N) и побитового XOR значения маски с целым числом, представляющим i ^-й символ строки, и увеличьте значение cnt на visible [mask] .
• Для каждого действительного i выполните итерацию по всем символам в диапазоне [a, z] и увеличьте его частоту, перевернув j- ^й бит набора в текущей маске, и увеличьте значение cnt на частоту битовой маски после переворачивания j ^-го установить бит.
• Значение, хранящееся в cnt , является требуемым ответом.

Ниже приведена реализация вышеуказанного подхода:

Временная сложность : O(N)
Вспомогательное пространство : O(N)