Last Updated: 20 Feb, 2021
Palindrome Permutation
Easy
Asked in companies
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
Approaches
- The idea behind this approach is that in a palindrome at max 1 character can have an odd frequency.
- 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.
- 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).
- After this we create a variable, (say ‘ODD’), that counts the number of characters which are having an odd frequency.
- 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.
- The idea behind this approach is the same as the last approach that in a palindrome, at max 1 character can have an odd frequency.
- But in this approach, we will not be storing the frequency of each character explicitly but use the bits of a variable to store the information about the frequency of each character.
- If we find any character in the string then we will toggle the bit corresponding to the current character.
- Therefore if a character will be having an odd frequency then the bit corresponding to that character will be 1 in the end or else it will be 0.
- So we will have a variable,(say ‘XORR’) which will be initialized to 0 so each bit of this variable is 0 initially.
- Then we will iterate through the given string and find the bit corresponding to the current character as (1<<(S[i] - ‘a’)). Then we will xor this value with our variable ‘XORR’ (i.e. ‘XORR’ = ‘XORR’ ^ (1 << (S[i] - ‘a’) ). If the bit corresponding to the current character was 0 then it will become 1 or else it will become 0.
- Finally, we only need to check that at max 1 bit is set in our variable ‘XORR’ which can be done in many ways. One way is that we can use some simple bit manipulation such as ('XORR' & ('XORR' - 1)), if this expression evaluates to zero then the variable xorr has at max 1 set bit in it or else it has more than 1 bit set in it.
- So if at max 1 bit is set in our variable ‘XORR’, then the string can be converted into a palindrome and the answer will be “True” or else it will be “False”.