Check Anagram String

Check Anagram Strings” is a very important and one of the most asked technical interview problems based on string data structure. 

Here, we are given two strings and our task is to check whether the strings are anagram of each other or not. 

Two strings are called anagram of each other if the characters and number of characters of the strings are same, but the order of characters of the strings does not matter. In Technical language, two strings are called anagram of each other if they are permutation of each other.

Example:

INPUT:
Str1 = “abcdfr”
Str2 = “frdcba”
OUTPUT:
The strings are anagram of each other
Explanation:
“abcdfr” can be rearranged to form string “frdcba”.
INPUT:
Str1 = “abcdfr”
Str2 = “frdcbx”
OUTPUT:
The strings are anagram of each other
Explanation:
“abcdfr” can be rearranged to form string “frdcbx”

There are various ways to check if two strings are anagram of each other or not. Some of them are:

METHOD  1: Sort and compare

The brute-force solution of the given problem is to sort the given strings and then check whether both the strings are equal or not after sorting. If they are equal, then the strings are anagram of each other. Else, strings are not anagram of each other.

The time complexity of this solution is O(nlogn), based on type of sorting algorithm used.

C++ Program to check whether the strings are anagram of each other or not is as follows:

#include<bits/stdc++.h>
using namespace std;
void checkAnagram(string str1,string str2)
{
    /* Sort the Strings */
    sort(str1.begin(),str1.end());
    sort(str2.begin(),str2.end());
    
    /* If Str1 is equal to Str2, then 
       strings are anagram of each other*/
    if(str1 == str2)
        cout<<"Strings are Anagram of each other\n";
    else
        cout<<"Strings are not Anagram of each other\n";
}
int main()
{
    string str1,str2;
    
    /* Scan the string */ 
    cout<<"Enter first string:\n";
    cin>>str1;
    cout<<"Enter second string:\n";
    cin>>str2;
    
    /* Function to check Anagram Strings */
    checkAnagram(str1,str2);
}
OUTPUT:
Enter first string:
ABBCD
Enter second string:
BBCAD
Strings are Anagram of each other

METHOD 2: Hashing Based

Hashing based solution is a more time efficient approach. 

We know we have 256 ASCII character set(0-255).

We will create an integer array of size 256 and initialize it with zero.

We will traverse the first string and for every character encountered in first string, we will increment the ascii position value in the array.

Now, we will traverse the second string and for every character encountered in the second string, we will decrement the ascii position value in the array.

Finally, we will check whether all the values of the array are zero or not. If they are zero, then the given two strings are anagram of each other, else they are not anagram of each other.

The time complexity of Hash Based solution is O(n).

C++ Program to check whether two strings are anagram of each other or not is as follows:

#include<bits/stdc++.h>
using namespace std;
void checkAnagram(string str1,string str2)
{
   int arr[256] = {0};
   int i;
   for(i = 0; i < str1.length(); i++)
   {
        arr[str1[i]]++;
   }
   for(i = 0; i < str2.length(); i++)
   {
        arr[str2[i]]--;
   }
   for(i = 0; i < 256; i++)
   {
       if(arr[i] != 0)
       {
            cout<<"The strings are not anagram of each other\n";
           return;
       }
   }
    cout<<"The strings are anagram of each other\n";
}
int main()
{
    string str1,str2;
    
    /* Scan the string */ 
    cout<<"Enter first string:\n";
    cin>>str1;
    cout<<"Enter second string:\n";
    cin>>str2;
    
    /* Function to check Anagram Strings */
    checkAnagram(str1,str2);
}
OUTPUT:
Enter first string:
ABBCD
Enter second string:
BBCAD
Strings are Anagram of each other

Related Posts:

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

You may also like...

Leave a Reply

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