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 check whether a string is Palindrome 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 a string is palindrome 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: 

#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. Program to print all the Palindromic Substring of the String.
  2. Program to check Panagram String.
  3. Program to find first non-repeating character of the String.
  4. Program to Reverse a String.
  5. Program to Count Number of Characters in a String.
  6. Program to Count frequency of particular character of the String.
  7. Program to Count Number of Vowels and Number of Consonants in a String.
  8. Program to Check if String is alphabetic or numeric or alpha-numeric.
  9. Program to copy one String to Another.
  10. Program to Concatenate Two Strings.
  11. Program to Check whether given String is Palindrome or not.
  12. Program to convert lower-case alphabet to upper-case alphabet and vice-versa.
  13. Program to count total number of words in a string.
  14. Program to find smallest and largest word of the String.
  15. Program to find Most Frequent Character of the String.
  16. Program to Remove all the blank spaces from the String.
  17. Program to check if String is isogram or not.
  18. Program to Reverse Each word of the String.
  19. Program to Print All the Substring of the Given String.
  20. Program to find longest palindromic Substring.

You may also like...

Leave a Reply

Your email address will not be published. Required fields are marked *