Problem description:

Given a string s, return true if a permutation of the string could form a palindrome.

Example 1:

1
2
Input: s = "code"
Output: false

Example 2:

1
2
Input: s = "aab"
Output: true

Example 3:

1
2
Input: s = "carerac"
Output: true

Constraints:

  • 1 <= s.length <= 5000
  • s consists of only lowercase English letters.

Solution:

Naive solution:

remove all character that have even number in string

check if the rest could make a valid palindrome

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
class Solution:
    def canPermutePalindrome(self, s: str) -> bool:
        '''
        find all invalid characters
        check if they could form palindrom
        
        '''
        def isValid(s):
            if not s: return True
            if len(s) == 1: return True
            l, r = 0, len(s)-1
            while l < r:
                if s[l] != s[r]: return False
                l, r = l+1, r-1
            return True
        
        def findInvalid(s):
            counter = Counter(s)
            res = ""
            for ch, freq in counter.items():
                print(freq, ch)
                if freq % 2:
                    res += ch*freq
            # print(res)
            return res
        
        while s:
            s = findInvalid(s)
            if isValid(s):
                return True
            else:
                return False
        return True

Only need to check if removing even number of characters, if the number of odd characters are greater than 1

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution:
    def canPermutePalindrome(self, s: str) -> bool:
        dic = defaultdict(int)
        for c in s:
            dic[c] += 1
        # return sum(v % 2 for v in dic.values()) < 2
        
        count1 = 0
        for val in dic.values():
            if val % 2 == 1:
                count1 += 1
            if count1 > 1:
                return False
        return True

time complexity: $O(n)$, n = len(s)
space complexity: $O(n)$
reference:
related problem: