Palindrome Permutation
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

Question

Palindrome Permutation

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

Accepted Answer

A set of characters can form a palindrome if at most one character occurs odd number of times and all characters occur even number of times.

This can be done in O(n) time using a count array.
Steps :
1. Create a count array of alphabet size which is typically 256. Initialize all values of count array as 0.
2. Traverse the given string and increment count of every character.
3. Traverse the count array and if the count array has more than one odd values, return false. Otherwise, return true.

Accepted Answer

Frequency Table

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.

Space Complexity: O(1)Explanation:

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

Time Complexity: O(n)Explanation:

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

C++ (g++ 5.4)

/*

    Time Complexity: O(N)

    Space Complexity: O(1)



    Where N is the length of the string.

*/



#include



bool palindromeString(string & s) {

    unordered_map < char, int > mp;

    for (int i = 0; i < s.size(); i++) {

        mp[s[i]]++;

    }



    int odd = 0;

    for (auto x: mp) {

        if ((x.second) % 2 == 1) {

            odd++;

        }



    }



    if (odd == 0 || odd == 1)

        return true;

    else

        return false;

}

Python (3.5)

'''

    Time Complexity: O(N)

    Space Complexity: O(1)



    Where N is the length of the string.

'''



def palindromeString(s):

    n = len(s)

    mp = dict()



    for i in range(n):

        if s[i] in mp:

            mp[s[i]] += 1

        else:

            mp[s[i]] = 1



    odd = 0

    for i in mp.values():

        if i % 2 == 1:

            odd += 1



    return odd <= 1

Java (SE 1.8)

/*

    Time Complexity: O(N)

    Space Complexity: O(1)



    Where N is the length of the string.

*/



import java.util.HashMap;



public class Solution {



    public static boolean palindromeString(String s) {



        HashMap < Character, Integer > mp = new HashMap < Character, Integer > ();

        for (int i = 0; i < s.length(); i++) {



            if (mp.containsKey(s.charAt(i))) {

                mp.put(s.charAt(i), mp.get(s.charAt(i)) + 1);

            } else {

                mp.put(s.charAt(i), 1);

            }



        }



        int odd = 0;

        for (int x: mp.values()) {

            if (x % 2 == 1) {

                odd++;

            }



        }



        if (odd == 0 || odd == 1)

            return true;

        else

            return false;

    }



}

Accepted Answer

Bit Manipulation

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

Space Complexity: O(1)Explanation:

O(1)

Since we are using constant space to keep the track of the frequency of each character, the space complexity is O(1).

Time Complexity: O(n)Explanation:

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

Since we iterate through the given string only once hence the time complexity will be O(N).

C++ (g++ 5.4)

/*

    Time Complexity: O(N)

    Space Complexity: O(1)



    Where N is the length of the string.

*/



bool palindromeString(string & s) {

    int xorr = 0;

    for (int i = 0; i < s.size(); i++) {

        int value = s[i] - 'a';

        int tempmask = (1 << value);

        xorr = xorr ^ tempmask;

    }



    return (xorr & (xorr - 1)) == 0;

}

Python (3.5)

'''

    Time Complexity: O(N)

    Space Complexity: O(1)



    Where N is the length of the string.

'''



def palindromeString(s):

    n = len(s)

    xorr = 0



    for i in range(n):

        value = ord(s[i]) - ord('a')

        tempmask = (1 << value)

        xorr = xorr ^ tempmask



    return (xorr & ( xorr - 1)) == 0

Java (SE 1.8)

/*

    Time Complexity: O(N)

    Space Complexity: O(1)



    Where N is the length of the string.

*/



public class Solution {



    public static boolean palindromeString(String s) {

        int xorr = 0;

        for (int i = 0; i < s.length(); i++) {

            int value = s.charAt(i) - 'a';

            int tempmask = (1 << value);

            xorr = xorr ^ tempmask;

        }



        return (xorr & (xorr - 1)) == 0;

    }



}

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

Note :

Example :

Input Format :

Output Format :

Note :

Constraints :

Top Hike Android Developer interview questions & answers

Popular interview questions of Android Developer

Top HR questions asked in Hike Android Developer