Description
https://leetcode.com/problems/palindrome-permutation/
Given a string s, return true if a permutation of the string could form a palindrome.
Example 1:
Input: s = "code" Output: false
Example 2:
Input: s = "aab" Output: true
Example 3:
Input: s = "carerac" Output: true
Constraints:
1 <= s.length <= 5000sconsists of only lowercase English letters.
Explanation
Count the occurrences of letters. If there are more than one letter occurs odds times, return False. Otherwise, return True.
Python Solution
class Solution:
def canPermutePalindrome(self, s: str) -> bool:
counter = {}
for c in s:
counter[c] = counter.get(c, 0) + 1
number_of_odds = 0
number_of_evens = 0
for key, value in counter.items():
if value % 2 == 0:
number_of_evens += 1
else:
number_of_odds += 1
if number_of_odds > 1:
return False
return True
- Time Complexity: O(N^2).
- Space Complexity: O(N).