Palindrome Permutation

Easy
0/40
Average time to solve is 15m
profile
Contributed by
13 upvotes
Asked in companies
MicrosoftHikeLinkedIn

Problem statement

You are given a string 'S', check if there exists any permutation of the given string that is a palindrome.

Note :

1. A palindrome is a word or phrase that reads the same from forward and backward e.g. “aba”, it reads the same from forward and backward.
2. A permutation is a rearrangement of letters.
3. The palindrome does not need to be limited to just dictionary words.

Example :

Given string S : aab
The output should be "True" as "aba" (permutation of string S) is a palindrome.
Detailed explanation ( Input/output format, Notes, Images )
Input Format : 
The first line of the input contains an integer 'T' denoting the number of test cases.

The first and the only line of each test case contains one string 'S'.
Output Format : 
For each test case print in a new line, “True” if any permutation of the string is a palindrome or “False” if none of the permutations of the given string are palindrome.
Note : 
You do not need to print anything, it has already been taken care of. Just implement the given function.
Constraints : 
1 <= T <= 10
1 <= Length of the given string <= 10^5
It is guaranteed that all the characters in the strings are lower case english alphabets.

Time Limit : 1sec
Sample Input 1 :
1
carrace
Sample Output 1 :
True
Explanation For Sample Input 1 :
The output is True because “racecar” is a permutation of “carrace” and it is a palindrome.
Sample Input 2 :
1
ferel
Sample Output 2 :
False
Explanation For Sample Input 2 :
Since no permutation of "ferel" is a palindrome hence the output is False.
Hint

We can use some special property of the palindromic string.

Approaches (2)
Frequency Table
  1. The idea behind this approach is that in a palindrome at max 1 character can have an odd frequency.
  2. So in this approach, we calculate the frequency of each character of the given string and check if at most 1 character has an odd frequency. If more than one character will be having the odd frequency then the given string can not be converted into a palindrome.
  3. Therefore, we create a frequency table, (say ‘MP’, and then iterate on each character for calculating the frequency(i.e. If ‘i’ is our iterating variable then ’MP'[S[i]] += 1).
  4. After this we create a variable, (say ‘ODD’), that counts the number of characters which are having an odd frequency.
  5. Finally, if the count variable is less than or equal to 1 then the given string can be converted into a palindrome, or else it can not be converted into a palindrome.
Time Complexity

O(N), where N is the length of the given string.

 

Firstly we calculate the frequency of each character and for that, we iterate on each character of the string once and for the checking that how many characters are having odd frequency we iterate on each character in the frequency table once and since its size can never be greater than 26, hence the overall time complexity will be O(N).

Space Complexity

O(1).

 

We store the frequency of each character in a frequency table, and only 26 different characters are possible so our complexity turns out to be O(26), which is almost constant and so the space complexity can be considered as O(1).

Code Solution
(100% EXP penalty)
Palindrome Permutation
Full screen
Console