Check whether two strings are anagram of each other

“Check whether two strings are anagram of each other” 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 two 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 whether two strings are anagram of each other. Some of them are:

METHOD  1: Sort and compare Technique to check whether two strings are anagram of each other

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 two strings are anagram of each other is as follows:

/* C++ Program to check whether two strings are anagram of each other */
#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 Approach to check whether two strings are anagram of each other

Hashing based solution is a more time efficient approach. 

As 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 is as follows:

/* C++ Program to check whether two strings are anagram of each other */
#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. Check Whether Given String is Palindromic Anagram or Not.
2. Check Whether Given String is Panagram or Not.
3. Find First Non-Repeating Character of the String.
4. Find Most Frequent Element of the Array.
5. Find Pair in an Array with Given Sum.
6. Find First Repeating Element of an Array.
7. Find Majority Element of an Array.
8. Find Most Frequent Character of the String.
9. Program to find first repeating element of an array.
10. Program to merge two sorted arrays.
11. Program to find missing number in an array.
12. Program to sort if array is sorted.
13. Program to print Alternate Elements of an Array.
14. Program to swap kth element from beginning to kth element from end in an Array.
15. Program to print all possible subarrays of the given array.
16. Program to print kth smallest and kth largest element of an Array.
17. Program to find equilibrium index of an Array.
18. Program to find majority element of an Array.
19. Program to find mean of the Array.
20. Program to check Idempotent Matrix.