# Palindrome Permutation

Write an efficient function that checks whether any permutation of an input string is a palindrome. You can assume the input string only contains lowercase letters.

Examples:

``````"civic" should return True
"ivicc" should return True
"civil" should return False
"livci" should return False``````

“But ‘ivicc’ isn’t a palindrome!”

But the question is asking if any permutation of the string is a palindrome. Spend some extra time ensuring you fully understand the question before starting. Jumping in with a flawed understanding of the problem doesn’t look good in an interview.

A permutaion of `ivicc -> icvci `is a palindrome

If a string with an even length is a palindrome, every character in the string must always occur an even number of times. If the string with an odd length is a palindrome, every character except one of the characters must always occur an even number of times. Thus, in case of a palindrome, the number of characters with odd number of occurrences can’t exceed 1.

Consider some examples:

```class Solution {
public boolean canPermutePalindrome(String s) {

if(s == null || s.isEmpty()){
return true;
}
Map<Character, Integer> map = new HashMap<>();
for(char ch : s.toCharArray()){
int count = map.getOrDefault(ch, 0);
map.put(ch, count+1);
}
int odd_count = 0;
for(char ch : map.keySet()){
int freq = map.get(ch);
if(freq % 2 != 0){
odd_count++;
}
if (odd_count > 1) {
return false;
}
}
return odd_count == 0 || odd_count == 1;
}
}
```

Complexity Analysis

• Time complexity : `O(n)`.
• Space Complexity : `O(1)`. The `map` can grow up to a maximum number of all distinct elements. However, the number of distinct characters are bounded (`26 for lower case a-z`), so as the space complexity.

Categories: String