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

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: