Check Whether Two Strings are Anagram of Each Others

DevSniper
Published : 23 July 2024

191 Views

String Data Structures Coding Problems DSA Challange Sliding Window

Given two strings str1 and str2 your task is to determine whether they are anagrams of each other or not.

An anagram string is a string that contains the exact same characters with the exact same frequencies as another string but the characters may be arranged in a different order. In simpler terms, two strings are anagrams of each other if they have the same characters in the same quantities, regardless of the order of those characters.

Example 1 :-

str1 : rebootmemory , str2 : rymerbmoooet

Output : Anagram

Example 2 :-

str1: rebootmemory, str2: reboottmemory

Output : Not Anagram

Constraints :

1 <= str1.length, str2.length <= 5 * 10^4
str1 and str2 consist of lowercase English letters

Approach 1 : Using Sorting

Strings will be Anagrams when two strings have exactly the same characters in the same frequencies. To Verify is two strings are anagrams, we can simply sort both strings and compare them. If the sorted versions of the strings are identical then the original strings are anagrams of each other.

C++

Java

Python

#include <bits/stdc++.h>
using namespace std;

bool isAnagrams(string str1,string str2)
{
    if(str1.length()!=str2.length()) {
        return false;
    }
    sort(str1.begin(), str1.end());
    sort(str2.begin(), str2.end());
    return str1==str2;
}
int main()
{
    string str1="rebootmemory";
    string str2="rymerbmoooet";
    if(isAnagrams(str1,str2)) {
        cout<<"Anagram"<<endl;
    } else {
        cout<<"Not Anagram"<<endl;
    }
}

Anagram

Time Complexity

We are use sorting so time complexity will be O(NlogN + MlogM) where N and M is the size of strings.

Space Complexity

We are not using any extra memory so Space Complexity : O(1)

Approach 2 : Counting Frequency

As we know if strings are anagram then strings have exactly the same characters in the same frequencies. and one more constraints that strings contains lowercase English letter, considering both we can determine if two strings are anagrams or not.

Steps :

Create a 26 size array to manage frequency of characters ( as per constraints strings contains only lower case English letters)
Iterate through str1 and count the frequency of each character.
Iterate through str2 and for each character decrement its frequency count if it exists in the frequency array, If a character does not exist in the frequency array, the strings are not anagrams.
After iterating through both strings if all characters have a frequency of zero in the frequency array then the strings are anagrams.

C++

Java

Python

#include <bits/stdc++.h>
using namespace std;

bool isAnagrams(string str1,string str2)
{
    if(str1.length()!=str2.length()) {
        return false;
    }
    int freq[26] = {0};
    for(int i=0; i<str1.length(); i++) {
        freq[str1[i]-'a']++;
    }
    for(int i=0; i<str2.length(); i++) {
        if(freq[str2[i]-'a']<1) {
            return false;
        }
        freq[str2[i]-'a']--;
    }
    for (int i = 0; i < 26; i++) {
        if (freq[i] != 0)
            return false;
    }
    return true;
}
int main()
{
    string str1="rebootmemory";
    string str2="rebmetmooory";
    if(isAnagrams(str1,str2)) {
        cout<<"Anagram"<<endl;
    } else {
        cout<<"Not Anagram"<<endl;
    }
}

Anagram

Time Complexity : O(M+N)

Space Complexity : O(1)

Approach 3 : Counting Frequency and Using Hashing

The idea is similar to above approach, Instead of using an array of size 26 to track character frequencies We can use HashMap to store the frequency of each characters.

Steps :

Create a HashMap to store frequency of characters.
Iterate through str1 and count the frequency of each character.
Iterate through str2 and for each character decrement its frequency count if it exists in the frequency map, If a character does not exist in the frequency map, the strings are not anagrams.
Iterate over map values if all values is zero then the strings are anagrams.

C++

Java

#include <bits/stdc++.h>
using namespace std;

bool isAnagrams(string str1,string str2)
{
    if(str1.length()!=str2.length()) {
        return false;
    }
    unordered_map<char, int> map;
    for(int i=0; i<str1.length(); i++) {
        map[str1[i]]++;
    }
    for(int i=0; i<str2.length(); i++) {
        if(map[str2[i]]<1) {
            return false;
        }
        map[str2[i]]--;
    }
    for (auto&amp; pair : map) {
        if (pair.second != 0)
            return true;
    }
}
int main()
{
    string str1="rebootmemory";
    string str2="rebmetmooory";
    if(isAnagrams(str1,str2)) {
        cout<<"Anagram"<<endl;
    } else {
        cout<<"Not Anagram"<<endl;
    }
}

Anagram

Time Complexity : O(M+N)

Space Complexity : O(K) where K is the unique characters in strings k => distinct( str1 and str 2 characters)