Строка называется палиндромом если она имеет абсолютно одинаковую последовательность символов с права на лево и слева на право, для примера:
- "kayak",
- "abcba",
- "neven".
Строка A называется анаграммой к строке B если A может быть получена из B путем перестановки символов. Для примера строки из этих пар являются анаграммами к друг другу:
- "mary" and "army",
- "rocketboys" and "octobersky",
- "divide" and "divide".
Необходимо написать функцию, которая для переданной непустой строки S состоящей из N символов вернет 1, если S - анаграмма какого-то полиндрома и вернет 0 в обратном случае.
Предполагаем:
- N число в диапазоне
[0..100,000]; - строка S состоит только из латинских букв в нижнем регистре (a−z).
Для примера, для строки S = "dooernedrn", функция должна вернуть 1, так как
"dooernedrn" анаграмма палиндрома "neroddoren". Для строки S = "aabcba",
функция должна вернуть 0.
Сложность алгоритма должна быть не более чем O(N) для худшего случая;