Problem

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

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 - 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.