266. Palindrome Permutation

class Solution:
    def canPermutePalindrome(self, s: str) -> bool:
        """
        main idea: check if there is at most one char has odd cnt 
        tc O(N) sc O(26) ~ O(1)
        """
        cnt = {}
        for c in s:
            if c not in cnt:
                cnt[c] = 1
            else:
                cnt[c] += 1 
        res = 0
        for v in cnt.values():
            if v%2 != 0 :
                res += 1
        return res <= 1 

class Solution:
    def canPermutePalindrome(self, s: str) -> bool:
        """
        tc O(N) sc O(26) ~ O(1)
        """
        cnt = 0 
        d = {}
        for c in s:
            if c not in d:
                d[c] = 1
            else:
                d[c] += 1
            if d[c]%2 == 1:
                cnt += 1
            else:
                cnt -= 1 
        return cnt <= 1 
        

class Solution:
    def canPermutePalindrome(self, s: str) -> bool:
        """
        tc O(N) sc O(26) ~ O(1)
        """
        cnt = 0 
        _set = set()
        for c in s:
            if c not in _set:
                _set.add(c)
            else:
                _set.remove(c)
        return len(_set)<= 1