Palindrome Permutation LeetCode Solution

Difficulty Level Easy
Frequently asked in Bloomberg Facebook Goldman Sachs Google Microsoft Uber
metaViews 3063

Problem Statement

Palindrome Permutation LeetCode Solution – We are given a string and asked if a permutation of the given string could form a palindrome.

Examples & Explanations

Example 1:

Input: s = "code"
Output: false
Explanation: we can not arrange letters of "code" to form a palindrome

Example 2:

Input: s = "aab"
Output: true
Explanation: permutation "aba" of given string is palindrome, hence true

Example 3:

Input: s = "carerac"
Output: true
Explanation: the given string is itself palindrome, there exists multiple permuations that form palindrome

Approach

To make a string palindrome, we need an even number of occurrences of letters so that the string reads the same from left and right. Let’s call this left and right occurrence of the letter “pair”. There can exist more than 1 pair of the same letter, eg. “aaaaaa” is also a palindrome. In case of an odd length of string, only one letter having no pair is allowed, .eg. “aaxaa”, ‘x’ does not has any partner hence does not form a pair. This should give us the intuition to solve this problem.

Algorithm

We will count the number of occurrences of each letter using a hashmap. Iterate through each letter in the string and increase the value of each char to count occurrences. After sorting all the counts of each letter, we look at the values.

  • if the count is even- this means it will help us to form palindrome, do nothing
  • if the count is odd-this means the palindrome is possible if no other letters have odd count values, keep a variable isCountOdd to keep a track when we encounter an odd count value
  • if isCountOdd is 1- this means we already have a letter that has occurred as odd so we look at the count value of the char
    • if it is even- do nothing
    • if it is odd- palindrome is not possible

Instead of using isCountOdd pointer, we can use another variable count which will store values of map%2. If all letters are appearing even times, the count will remain 0. In case of odd occurrences, the count will get incremented by 1. if the count ≤ 1 ⇒ palindrome is possible. This approach is shown in java code.

Code

C++ code for Palindrome Permutation LeetCode Solution

class Solution {
public:
    bool canPermutePalindrome(string s) {
        unordered_map<char,int> cnt;
        int n=s.size();
        for(int i=0; i<n; i++) {
            cnt[s[i]]++;
        }
        int isCountOdd=0;
        
        for(auto it:cnt){
            if(isCountOdd==1 && it.second%2!=0) return 0;
            else if(it.second%2!=0) isCountOdd++;
            else continue;
        }
        return 1;
    }
};

Java code for Palindrome Permutation LeetCode Solution

public class Solution {
    public boolean canPermutePalindrome(String s) {
        int[] map = new int[128];
        for (int i = 0; i < s.length(); i++) {
            map[s.charAt(i)]++;
        }
        int count = 0;
        for (int key = 0; key < map.length && count <= 1; key++) {
            count += map[key] % 2;
        }
        return count <= 1;
    }
}

Complexity Analysis

  • Time complexity: O(n)
    • 2 loops are used, one to count the occurrences taking O(n) and another to traverse on distinct elements of string s again taking O(n) time in the worst case i.e all characters in s are distinct
  • Space complexity: O(1)
    • The map can grow up to a maximum number of all distinct elements. However, the number of distinct characters is bounded, and so is the space complexity.
Translate »