# Palindrome Permutation

Posted: 20 Feb, 2021
Difficulty: Easy

## PROBLEM STATEMENT

#### 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.