As we build {char -> count} map, we can find out the count of characters that appear odd number of times. For a palindrome there can be at most 1 such character.
Time: 
class Solution:
def canPermutePalindrome(self, s: str) -> bool:
odd_char_count = 0
char_count = {}
for c in s:
char_count[c] = char_count.get(c, 0) + 1
odd_char_count += (1 if char_count[c] % 2 == 1 else -1)
return odd_char_count < 2
We can also maintain a set of characters that appear odd number of times.
class Solution:
def canPermutePalindrome(self, s: str) -> bool:
odd_chars = set()
for c in s:
if c in odd_chars:
odd_chars.remove(c)
else:
odd_chars.add(c)
return len(odd_chars) < 2
unreasonably effective 
Leave a comment