An anagram string is a rearrangement of the letters of a given string to form another word or phrase, using all the original letters exactly once. For example, “listen” and “silent” are string anagrams of each other. In this article, we will be delving into what is anagram string.
Problem Statement
Given two strings consisting of lowercase English alphabets, print YES if they are anagram of each other, else print NO.
Note: Two strings s1 and s2 are an anagram of each other if both the strings contain the same set of characters and the frequency of each character in s1 and s2 are also the same but the order of characters in the strings may or may not be the same.
Example
Input : s1 = “ababbc”, s2=”babbac”
Output: YES
Explanation: In the above example, we can see that the string s1 contains 2 ‘a’ characters, 3 ‘b’ characters, and 1 ‘c’ character and the string s2 also contains 2 ‘a’ characters, 3 ‘b’ characters, and 1 ‘c’ character. So the strings s1 and s2 are an anagram of each other because the frequency of ‘a’, ‘b’, and ‘c’ in both the string is the same.
Example
Input : s1 = “ababbc”, s2=”abbaac”
Output: NO
Explanation: In the second example, we can see that the string s1 contains 2 ‘a’ characters, 3 ‘b’ characters, and 1 ‘c’ characters but the string s2 contains 3 ‘a’ characters, 2 ‘b’ characters, and 1 ‘c’ character. So the strings s1 and s2 are not an anagram of each other because the frequency of ‘a’, ‘b’, and ‘c’ in both strings are not the same.
Approach 1: Using Sorting
In this approach, we will use sorting to check anagram of string. We will use the concept that if both the strings are sorted, then they must become equal if they are an anagram of each other because each character of s1 will match with each corresponding character of s2 starting from left to right. So after sorting both the strings, if they become equal we will return true, else we will return false.
Algorithm
- Let the given strings be s1 of length n and s2 of length m
- First check if n is equal to m or not, if they are not equal, print NO and return
- Sort both the strings s1 and s2.
- Check if s1 is equal to s2 or not, if they are equal then print YES, else print NO.
C++ Implementation
#include<bits/stdc++.h>
using namespace std;
int areAnagramStrings(string &s1,string &s2,int n,int m){
if(n!=m)
return false;
sort(s1.begin(),s1.end()); // sort string s1
sort(s2.begin(),s2.end()); // sort string s2
if(s1==s2) // if they are equal then return true
return true;
else // else if they are not equal return false
return false;
}
int main(){
string s1 = "ababbc";
string s2 = "babbac";
bool k = areAnagramStrings(s1,s2,s1.length(),s2.length());
if(k)
cout<<"YES";
else
cout<<"NO";
return 0;
}
Java Implementation
public class nEvenSum{
static boolean areAnagramStrings(String s1,String s2,int n,int m){
if(n!=m)
return false;
char charArray1[] = s1.toCharArray();
Arrays.sort(charArray1); // sort string s1
String string1 = new String(charArray1);
char charArray2[] = s2.toCharArray();
Arrays.sort(charArray2); // sort string s2
String string2 = new String(charArray2);
for(int i=0;i<n;i++){
if(string1.charAt(i)!=string2.charAt(i)) // if they are not equal return false
return false;
}
return true; // else if they are equal return true
}
public static void main(String argc[]){
String s1 = "ababbc";
String s2 = "babbac";
boolean k = areAnagramStrings(s1,s2,s1.length(),s2.length());
if(k)
System.out.println("YES");
else
System.out.println("NO");
}
}
Python Implementation
def areAnagramStrings(s1,s2,n,m):
if(n!=m):
return False
if(sorted(s1) == sorted(s2)): # if both the strings are equal after sorting
return True # then return true
else:
return False # else return false
s1 = "ababbc"
s2 = "babbac"
k = areAnagramStrings(s1,s2,len(s1),len(s2))
if(k==True):
print("YES")
else:
print("NO")
Output
YES
Complexity Analysis
Time Complexity: O(N*LogN), due to sorting both strings.
Space Complexity: O(1), as it doesn’t require additional space.
Approach 2: Count Characters
In this method, we create two arrays, arr1 and arr2, each of size 26 to store character frequencies of strings s1 and s2 respectively. We compare the frequencies of corresponding characters. If any differ, we return false; otherwise, true. This approach utilizes hashing and can alternatively be implemented using a map.
Algorithm
- Create two arrays, arr1 and arr2, each of size 26.
- Initialize both arrays with zeros.
- Iterate through s1 and s2, incrementing the respective character frequencies in arr1 and arr2.
- Compare corresponding elements of arr1 and arr2.
- If any element differs, return false; otherwise, return true.
- Ensure s1 and s2 have equal lengths before proceeding.
C++ Implementation
#include<bits/stdc++.h>
using namespace std;
int areAnagramStrings(string &s1,string &s2,int n,int m){
if(n!=m)
return false;
vector<int> arr1(26,0); // Creating arr1 and initializing all elements with 0
vector<int> arr2(26,0); // Creating arr2 and initializing all elements with 0
int i;
for(i=0;i<n;i++){
arr1[s1[i]-'a']++; // Counting frequency of characters in s1
}
for(i=0;i<n;i++){
arr2[s2[i]-'a']++; // Counting frequency of characters in s2
}
for(i=0;i<26;i++){
if(arr1[i]!=arr2[i]) // If frequency of any character does not match, return false
return false;
}
return true; // else return true
}
int main(){
string s1 = "ababbc";
string s2 = "babbac";
bool k = areAnagramStrings(s1,s2,s1.length(),s2.length());
if(k)
cout<<"YES";
else
cout<<"NO";
return 0;
}
Java Implementation
public class nEvenSum{
static boolean areAnagramStrings(char s1[], char s2[],int n,int m){
if(n!=m)
return false;
int arr1[] = new int[26];
Arrays.fill(arr1, 0); // Creating arr1 and initializing all elements with 0
int arr2[] = new int[26];
Arrays.fill(arr2, 0); // Creating arr2 and initializing all elements with 0
int i;
for(i=0;i<n;i++){
arr1[s1[i]-'a']++; // Counting frequency of characters in s1
}
for(i=0;i<n;i++){
arr2[s2[i]-'a']++; // Counting frequency of characters in s2
}
for(i=0;i<26;i++){
if(arr1[i]!=arr2[i])
return false; // If frequency of any character does not match, return false
return false;
}
return true; // else return true
}
public static void main(String argc[]){
char s1[] = ("ababbc").toCharArray();
char s2[] = ("babbac").toCharArray();
boolean k = areAnagramStrings(s1,s2,s1.length,s2.length);
if(k)
System.out.println("YES");
else
System.out.println("NO");
}
}
Python Implementation
def areAnagramStrings(s1,s2,n,m):
if(n!=m):
return False
arr1 = [0] * 26 # Creating arr1 and initializing all elements with 0
arr2 = [0] * 26 # Creating arr2 and initializing all elements with 0
for x in s1:
arr1[ord(x)-ord('a')] += 1 # Counting frequency of characters in s1
for y in s2:
arr2[ord(y)-ord('a')] += 1 # Counting frequency of characters in s2
for i in range(26):
if arr1[i] != arr2[i]: # If frequency of any character does not match, return false
return False
return True # else return true
s1 = "ababbc"
s2 = "babbac"
k = areAnagramStrings(s1,s2,len(s1),len(s2))
if(k==True):
print("YES")
else:
print("NO")
Output
YES
Complexity Analysis
Time Complexity: O(N), as it traverses each string once.
Space Complexity: O(1), as it uses fixed-size arrays.
Approach 3: Using hashing
In this approach, we leverage hashing techniques to determine if two strings are anagrams. We’ll employ the properties of hash functions to efficiently compare the characters and their frequencies in both strings.
Algorithm
- Let the given strings be s1 of length n and s2 of length m, first check if n is equal to m or not, if they are not equal, return false.
- Create the map mp of <character,integer>.
- Run a for loop from i=0 to i=n-1 and increase the frequency of every character in s1 i.e. perform the operation mp[s1[i]]++
- Run a for loop again from i=0 to i=n-1 and decrease the frequency of every character in s2 i.e. perform the operation mp[s2[i]]–
- Finally, check all the elements of the map, if at any moment we found that the frequency of any character in the map is not equal to 0, we will return false, else we will return true
C++ Implementation
#include<bits/stdc++.h>
using namespace std;
int areAnagramStrings(string &s1,string &s2,int n,int m){
if(n!=m)
return false;
unordered_map<char,int> mp; // Creating the hashmap
int i;
for(i=0;i<n;i++){
mp[s1[i]]++; // Increasing the frequency of characters in s1
}
for(i=0;i<n;i++){
mp[s2[i]]--; // Decreasing the frequency of characters in s2
}
for(auto x:mp){
if(x.second!=0)
return false; // finally if frequency of all elements is not 0, return false
}
return true; // else return true
}
int main(){
string s1 = "ababbc";
string s2 = "babbac";
bool k = areAnagramStrings(s1,s2,s1.length(),s2.length());
if(k)
cout<<"YES";
else
cout<<"NO";
return 0;
}
Java Implementation
public class nEvenSum{
static boolean areAnagramStrings(String s1, String s2,int n,int m){
if(n!=m)
return false;
HashMap<Character, Integer> mp = new HashMap<>(); // Creating the hashmap
int i;
for (i=0;i<n;i++) {
if (mp.containsKey(s1.charAt(i)))
mp.put(s1.charAt(i),mp.get(s1.charAt(i)) + 1); // Increasing the frequency of characters in s1
else
mp.put(s1.charAt(i), 1);
}
for (i=0;i<m;i++) {
if (mp.containsKey(s2.charAt(i)))
mp.put(s2.charAt(i),mp.get(s2.charAt(i)) - 1); // Decreasing the frequency of characters in s2
}
Set<Character> pair = mp.keySet();
for (Character key : pair) {
if (mp.get(key) != 0) { // finally if frequency of all elements is not 0, return false
return false;
}
}
return true; // else return true
}
public static void main(String argc[]){
String s1 = "ababbc";
String s2 = "babbac";
boolean k = areAnagramStrings(s1,s2,s1.length(),s2.length());
if(k)
System.out.println("YES");
else
System.out.println("NO");
}
}
Python Implementation
def areAnagramStrings(s1,s2,n,m):
if(n!=m):
return False
map = {} # Creating the hashmap
for x in s1:
if (x in map):
map[x] += 1 # Increasing the frequency of characters in s1
else:
map[x] = 1
for y in s2:
if (y in map):
map[y] -= 1 # Decreasing the frequency of characters in s2
pair = map.keys()
for key in pair:
if (map[key] != 0): # finally if frequency of all elements is not 0, return false
return False
return True # else return true
s1 = "ababbc"
s2 = "babbac"
k = areAnagramStrings(s1,s2,len(s1),len(s2))
if(k==True):
print("YES")
else:
print("NO")
Output
YES
Complexity Analysis
Time Complexity: O(N), as it traverses each string once.
Space Complexity: O(1), as it uses a hashmap with a fixed-size character set.
Conclusion
- This article explored various approaches to determine whether two strings are anagrams of each other.
- The sorting approach involves sorting both strings and comparing them, which has a time complexity of O(n log n).
- Counting characters utilizes character counting to compare the frequency of characters in both strings, with a time complexity of O(n).
- Using hashing employs hash functions to efficiently compare character frequencies, also with a time complexity of O(n).
