Problem Statement: Given two strings, check if two strings are anagrams of each other or not.
Examples:
Example 1: Input: CAT, ACT Output: true Explanation: Since the count of every letter of both strings are equal. Example 2: Input: RULES, LESRT Output: false Explanation: Since the count of U and T is not equal in both strings.
Solution
Disclaimer: Don’t jump directly to the solution, try it out yourself first.
Solution 1:
Approach: Sort both the string and compare each and every letter of both strings. If all letters matched then, print true. Otherwise, print false.
For Eg.
We have
Str1 = “INTEGER”
Str2=”TEGERNI”
After sorting Str1 and Str2, we find that both of the strings are
Str1 =” EEGINRT”
Str2=” EEGINRT”
Since both of the strings are the same, this means both Str1 and Str2 are anagrams of each other.
Code:
C++ Code
#include <iostream>
#include <algorithm>
using namespace std;
bool CheckAnagrams(string str1, string str2)
{
// Case 1: when both of the strings have different lengths
if (str1.length() != str2.length())
return false;
sort(str1.begin(), str1.end());
sort(str2.begin(), str2.end());
// Case 2: check if every character of str1 and str2 matches with each other
for (int i = 0; i < str1.length(); i++)
{
if (str1[i] != str2[i])
return false;
}
return true;
}
int main()
{
string Str1 = "INTEGER";
string Str2 = "TEGERNI";
if(CheckAnagrams(Str1, Str2))
cout << "True" << endl;
else
cout<<"False"<<endl;
return 0;
}
Output: True
Time Complexity: O(nlogn) since sorting function requires nlogn iterations.
Space Complexity: O(1)
Java Code
import java.util.*;
public class Main
{
public static String SortString(String str)
{
char c[] = str.toCharArray();
Arrays.sort(c);
return new String(c);
}
public static boolean checkAnagrams(String str1, String str2)
{
// Case 1: when both of the strings have different lengths
if (str1.length() != str2.length())
return false;
str1 = SortString(str1);
str2 = SortString(str2);
// Case 2: check if every character of str1 and str2 matches with each other
for (int i = 0; i < str1.length(); i++)
{
if (str1.charAt(i) != str2.charAt(i))
return false;
}
return true;
}
public static void main(String args[])
{
String Str1 = "INTEGER";
String Str2 = "TEGERNI";
System.out.println(checkAnagrams(Str1, Str2));
}
}
Output: True
Time Complexity: O(nlogn) since sorting function requires nlogn iterations.
Space Complexity: O(1)
Solution 2:
Approach: Just count the frequency of every element in Str1 and iterate through Str2 and decrease the count of every element in the frequency array. Now iterate again, if the frequency at any point is not 0 this means, strings are not anagrams of each other.
For Eg,
Str1 = ”INTEGER”
Str2 = ”NTEGERI”
Frequency array of every element :
We check for every element of Str2 and find that all elements are found, so return true.
Code:
C++ Code
#include <iostream>
#include <algorithm>
using namespace std;
bool CheckAnagrams(string str1, string str2)
{
// when both of the strings have different lengths
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++)
{
freq[str2[i] - 'A']--;
}
for (int i = 0; i < 26; i++)
{
if (freq[i] != 0)
return false;
}
return true;
}
int main()
{
string Str1 = "INTEGER";
string Str2 = "TEGERNI";
if(CheckAnagrams(Str1, Str2))
cout << "True" << endl;
else
cout<<"False"<<endl;
return 0;
}
Output: True
Time Complexity: O(n) where n is the length of string
Space Complexity: O(1)
Java Code
import java.util.*;
public class Main {
public static boolean checkAnagrams(String str1, String str2) {
// when both of the strings have different lengths
if (str1.length() != str2.length())
return false;
int[] freq = new int[26];
for (int i = 0; i < str1.length(); i++) {
freq[str1.charAt(i) - 'A']++;
}
for (int i = 0; i < str2.length(); i++) {
freq[str2.charAt(i) - 'A']--;
}
for (int i = 0; i < 26; i++) {
if (freq[i] != 0)
return false;
}
return true;
}
public static void main(String args[]) {
String Str1 = "INTEGER";
String Str2 = "TEGERNI";
System.out.println(checkAnagrams(Str1, Str2));
}
}
Output: true
Time Complexity: O(n) where n is the length of string
Space Complexity: O(1)
Special thanks to Gurmeet Singh for contributing to this article on takeUforward. If you also wish to share your knowledge with the takeUforward fam, please check out this article