266. Palindrome Permutation - Explanation

Description

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

A palindrome is a string that reads the same forward and backward.

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.

Company Tags

Please upgrade to NeetCode Pro to view company tags.

1. Brute Force

class Solution:
    def canPermutePalindrome(self, s: str) -> bool:
        count = 0
        for i in range(128):  # For all ASCII characters
            if count > 1:
                break
            ct = 0
            for j in range(len(s)):
                if s[j] == chr(i):  # Comparing with ASCII character
                    ct += 1
            count += ct % 2
        return count <= 1

Time & Space Complexity

Time complexity: $O(n)$ $O (n)$
- If we generalize the solution to handle any Unicode character (no hardcoding): $O(k \cdot n)$ .
  $O(n^2)$ In the worst case, if all characters are unique $(k = n)$
Space complexity: $O(1)$ $O (1)$ If the we assume the input contains only ASCII characters.
- $O(1)$ If the implementation is modiifed to handle Unicode characters.

Where $n$ is the size of the input string s and where $k$ is the number of unique characters in s

2. Using HashMap

class Solution:
    def canPermutePalindrome(self, s: str) -> bool:
        from collections import Counter

        count = Counter(s)
        odds = sum(val % 2 for val in count.values())
        return odds <= 1

Time & Space Complexity

Time complexity: $O(n)$ $O (n)$
- $O(n + k)$ If we generalize the solution to handle any Unicode character. In the worst case $(k = n)$ , this becomes $O(n)$ .
Space complexity: $O(1)$ $O (1)$ If the we assume the input contains only ASCII characters.
- $O(k)$ If the implementation is modiifed to handle Unicode characters, the space complexity would depend on the number of unique characters in the string. $O(n)$ in the worst case (if all characters are unique).

Where $n$ is the size of the input string s and where $k$ is the number of unique characters in s

3. Using Array

class Solution:
    def canPermutePalindrome(self, s: str) -> bool:
        map = [0] * 128
        for ch in s:
            map[ord(ch)] += 1
        count = 0
        for c in map:
            if c % 2:
                count += 1
        return count <= 1

Time & Space Complexity

Time complexity: $O(n)$
Space complexity: $O(1)$ $O (1)$ If the we assume the input contains only ASCII characters.
- $O(k)$ If the implementation is modiifed to handle Unicode characters, the space complexity would depend on the number of unique characters in the string. $O(n)$ in the worst case (if all characters are unique).

Where $n$ is the size of the input string s and where $k$ is the number of unique characters in s

4. Single Pass

class Solution:
    def canPermutePalindrome(self, s: str) -> bool:
        map = [0] * 128
        count = 0
        for i in range(len(s)):
            map[ord(s[i])] += 1
            if map[ord(s[i])] % 2 == 0:
                count -= 1
            else:
                count += 1
        return count <= 1

Time & Space Complexity

Time complexity: $O(n)$
Space complexity: $O(1)$ $O (1)$ If the we assume the input contains only ASCII characters.
- $O(k)$ If the implementation is modiifed to handle Unicode characters, the space complexity would depend on the number of unique characters in the string. $O(n)$ in the worst case (if all characters are unique).

Where $n$ is the size of the input string s and where $k$ is the number of unique characters in s

5. Using Set

class Solution:
    def canPermutePalindrome(self, s: str) -> bool:
        chars = set()
        for c in s:
            if c in chars:
                chars.remove(c)
            else:
                chars.add(c)
        return len(chars) <= 1

Time & Space Complexity

Time complexity: $O(n)$
Space complexity: $O(1)$ $O (1)$ If the we assume the input contains only ASCII characters.
- $O(k)$ If the implementation is modiifed to handle Unicode characters, the space complexity would depend on the number of unique characters in the string. $O(n)$ in the worst case (if all characters are unique)

Where $n$ is the size of the input string s and where $k$ is the number of unique characters in s