LeetCode 266. Palindrome Permutation

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 <= 5000
  • s consists 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).

Leave a Reply

Your email address will not be published.