Palindrome Permutation

Problem

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

OR

Check if any anagram of a string is a Palindrome or not.

Examples

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

Solution

Method 1 - Naive approach of rotating input string

The most straightforward (but highly inefficient) solution is to generate all possible permutations of the input string and check each one to see if it forms a palindrome. If any permutation is a palindrome, return true; otherwise, return false. This brute-force approach is extremely slow for longer strings, since the number of permutations grows factorially with the string length (O(n!)).

Method 2 - Using Frequency Map

For a string to be rearranged into a palindrome:

• All characters must appear an even number of times, allowing them to be mirrored around the centre, except for at most one character which can appear an odd number of times (this would be the centre character in an odd-length palindrome).

Approach

1. Count the frequency of each character in the string.
2. Check how many characters have an odd frequency.
3. If more than one character has an odd frequency, return false; otherwise, return true.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

class Solution {
    public boolean canPermutePalindrome(String s) {
        Map<Character, Integer> charCount = new HashMap<>();
        for (char ch : s.toCharArray()) {
            charCount.put(ch, charCount.getOrDefault(ch, 0) + 1);
        }
        
        int oddCount = 0;
        for (int count : charCount.values()) {
            if (count % 2 == 1) {
                oddCount++;
            }
        }
        
        return oddCount <= 1;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

class Solution:
    def canPermutePalindrome(self, s: str) -> bool:
        char_count = {}
        for char in s:
            char_count[char] = char_count.get(char, 0) + 1
        
        odd_count = 0
        for count in char_count.values():
            if count % 2 == 1:
                odd_count += 1
        
        return odd_count <= 1

Complexity

• ⏰ Time complexity: O(n) where n is the length of the string. This is due to counting the frequency of characters and then checking the counts.
• 🧺 Space complexity: O(1) if only considering the fixed number of possible characters (e.g., ASCII or a limited character set). This is because the space for counting is constant irrespective of the length of string.