Check Whether String is Palindromic Anagram or Not

“Check Whether String is Palindromic Anagram or Not” is popular interview problem asked in many technical and algorithmic interviews. Here, we are given a string and our task is to write a program to check whether string is Palindromic Anagram or not. 

A palindrome Anagram string is a string which can be rearranged to form a palindrome. In technical language, any permutation of given string is palindrome.

Example:

INPUT:
AABBC
OUTPUT:
AABBC is palindromic Anagram
Explanation:
AABBC can be rearranged into ABCBA which is an palindrome.

Properties of Palindromic string

1. A palindromic string is a string that can read same from forward or backward. Examples are: “MADAM”, “NITIN”.

2. If the string is even length string, then the frequency of all the characters of the string must be even, then only it can be palindromic anagram.

3. If the string is odd length string, then the frequency of all the characters of the string must be even, except one character, which will have odd frequency, then only it can be palindromic anagram.

SOLUTION:

The steps required to check whether string is palindromic anagram or not are as follows:

1. Check whether the string is odd length of even length.
2. Store the frequency of every character of string in the hash map.
3. If the string is even length string, traverse the hashmap and check whether frequency of all the character is even or not. If frequency of each character in the string is even, then the given string is palindromic anagram string. Else, the given string is not palindromic anagram.
4. If the string is odd length string, traverse the hashmap and check whether frequency of all the character is even or not, except one character which will have odd frequency. If this condition holds, then the given string is palindromic anagram string. Else, the given string is not palindromic anagram.

The time complexity of this solution is O(nlogn), where ‘n’ is the length of the string and ‘logn’ for inserting and searching in the map.

C++ Program to check whether string is Palindromic Anagram or not is as follows: 

/* C++ Program to check whether string is Palindromic Anagram or not */
#include<bits/stdc++.h>
using namespace std;
void checkPalindrome(string str)
{
    int len = str.length();
    int i;
    map<int,int>mp;
    map<int,int> :: iterator itr;
    for(i=0;i<len;i++)
    mp[str[i]]++;
    // If the length of string is even, then
    // to form a palindrome all the frequency
    // of characters must be even
    if(len % 2 == 0)
    {
        for(itr = mp.begin() ; itr!=mp.end() ; ++itr)
        {
            if(itr -> second % 2 != 0)
            {
                cout<<"The string is not palindrome Anagram\n";
                return;
            }
        }
        cout<<"The string is palindrome Anagram\n";
    }
    // Else,to form a palindrome all the frequency
    // of characters must be even except frequency
    // of one character
    else
    {
        int flag = 0;
        for(itr = mp.begin() ; itr!=mp.end() ; ++itr)
        {
            if(itr -> second % 2 != 0)
            {
                flag++;
            }
        }
        // only one character with odd frequency
        if(flag == 1)
            cout<<"The string is palindrome Anagram\n";
        else
            cout<<"The string is not palindrome Anagram\n";
    }
}
int main()
{
    string str;
    /* Scan String */
    cout<<"Enter a string:\n";
    cin>>str;
    /* Check if string is Palindromic Anagram */
    checkPalindrome(str);
}

Output:
Enter a string:
AABBCCD
The string is palindrome Anagram

Related Posts:

1. Check Whether Given String is Panagram or Not.
2. Find First Non-Repeating Character of the String.
3. Find Most Frequent Element of the Array.
4. Find Pair in an Array with Given Sum.
5. Find First Repeating Element of an Array.
6. Find Majority Element of an Array.
7. Find Most Frequent Character of the String.
8. Check Anagram Strings.
9. Find Minimum number of bracket reversals required to make an expression balanced.
10. Implement Queue Using Two Stacks.
11. Merge Overlapping Intervals using Stacks
12. Implement Stack Using Linked List
13. Largest Rectangular Area in Histogram
14. Length of Longest Valid Substring
15. Reverse a String using Stack
16. Implement two stacks in a single array
17. Print Bracket Number
18. Program to find LCM of two numbers.
19. Next Greater Frequency Element
20. Sort a Stack using Temporary Stack