В общем то базовая задачка: дана строка из символов 'a' - 'z'. Нужно проверить можно ли сделать из строки палиндром
СНАЧАЛА СМОТРИМ БАЗУ, а потом самый сок
Идея решения: подсчитать число каждой буквы. Если все буквы имеют четное число - то точно палиндром
Если все четные кроме одного - тоже палиндром можем получить
В остальных случаях false
Базовое решение выглядит так
def can_be_palindrome(s: str) -> bool:
freq = {}
for ch in s:
freq[ch] = freq.get(ch, 0) + 1
odd_count = 0
for count in freq.values():
if count % 2 != 0:
odd_count += 1
return odd_count <= 1
НО! Если ты олимпиадник, то вот эти все решения не для тебя
Ты на изи воспользуешься свойсвом ascii таблицы что все символы идут подряд и уместишь их в int32
ШАХ и МАТ!
def can_be_palindrome(s: str) -> bool:
mask = 0
for ch in s:
bit = ord(ch) - ord('a')
mask ^= (1 << bit)
return mask == 0 or (mask & (mask - 1)) == 0
Ну и это, 🌭 бахни, по-братски)