Check If Two Strings are Anagram

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.

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

Java Implementation

Python Implementation

Output

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

Java Implementation

Python Implementation

Output

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

Java Implementation

Python Implementation

Output

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.