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:

StringLengthis Palindrome
aabbEvenYes as odd occurrence character is 0
aaabcccEvenNo as odd occurrence character is 3 – a,b and c
abbOddYes as odd occurrence character is 1 – a
aaabbbEvenNo, as odd occurrence characters are 2 – a and b
Why odd occurrence character should be 0 or 1
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

1 reply

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s