Palindrome Permutation

Posted: 20 Feb, 2021
Difficulty: Easy

PROBLEM STATEMENT

Try Problem

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. 
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
Approach 1
  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.
Try Problem