Python Program to Check Whether Two Strings are Anagram to Each Other or Not

An Anagram is a word or phrase formed by rearranging the letters of a different word or phrase.

For example, the word "listen" is an anagram of "silent", and "fired" is an anagram of "fried" and vice versa.

You are given two strings, and the problem is finding whether both strings are anagrams to each other or not.

Example 1:

Example 2:

Method 1 - Using sorting to check whether the given strings are anagrams or not

The program can be summarized as follows:

• Sort both strings,
• Compare both strings using the equal operator (==)
• Print 'Anagrams' if they are equal
• Else, print 'Not Anagrams'

Output:

 The two strings are anagrams. 

Explanation:

The isAnangram function first checks whether string lengths are the same or not. The function returns false if the lengths are different, stating that the strings cannot be anagrams of each other. If the lengths are the same, the function sorts and compares the characters in each string. The function returns True if the sorted strings are the same, indicating that the original strings are anagrams. If the sorted strings are not the same, the original strings are not anagrams, and the function returns False.

Time Complexity - O(n*logn): The sorting operation has the time complexity = O(n*logn).

Space Complexity - O(n): Extra space is needed to store the sorted strings.

Method 2 - Using an array to store the count of each character.

The program can be summarized as follows:

• Check whether the given strings are of the same length or not. If not, then return false. If yes, follow the following steps.
• Create an array of size 26 initialized with zero
• For each character in string one, increase the frequency of the character at the respective index in the array
• For each character in string two, increase the frequency of the character at the respective index in the array
• At any instance, if the value at any index becomes negative, return false
• Else, return True

Output:

 The two strings are anagrams. 

Explanation:

The isAnangram function first checks whether string lengths are the same or not. The function returns false if the lengths are different, stating that the strings cannot be anagrams of each other.

The function then initializes a frequency array freq of size 26 (for the 26 English alphabets) to count the frequency of each character in the first string str1. The frequency of each character is stored in the corresponding index of the freq array, using the ASCII values of the characters.

The function then iterates over the characters in the second string str2 and decrements the frequency of each character in the freq array. If the frequency of a character in str2 is greater than the frequency in str1, then the strings cannot be anagrams, and the function returns False.

The function returns True if the frequency of characters in str1 and str2 are the same.

Time Complexity - O(n): The program iterates over each character of both strings, which makes its time complexity equal to O(n).

Space Complexity - O(1): No extra space is needed. The size of the array is fixed for all 26 alphabets.

Method 3 - Use a dictionary to count the frequency of characters.

The program can be summarized as follows:

• Check whether the given strings are of the same length or not. If not, then return false. If yes, follow the following steps.
• For each character in string one, make a key and assign the frequency as the value to that key.
• For each character in string two, check whether the key is present or not.
• If the key is not present or the frequency for that character is zero, return False.
• Else, decrease the frequency by one for that key.
• At the end of the program, return True.

Output:

 The two strings are anagrams. 

Explanation:

The isAnagram() function first creates an empty dictionary to store the frequency of each character in string 1. It then iterates over each character of string one using for loop, makes the character a key if it is not present, and then increments the frequency by one each time for that character.

It then iterates over each character of string two using for loop and checks if the key is present in the dictionary or not or if the frequency of the character is zero or not. If any of the conditions are satisfied, it returns false.

It decrements the frequency of each character one by one and returns True at the end of the program, indicating that both the strings are anagrams.

Time Complexity - O(n): The program uses for-loop to iterate over both strings

Space Complexity - O(n): It uses a dictionary to store the frequency. The size of the dictionary depends on the length of the string.

Method 4 - Using Counter() from collections

The program can be summarized as follows:

• Import Counter form collections.
• Check whether the given strings are of the same length or not. If not, then return false. If yes, follow the following steps.
• Create two counters, one for string one and one for string two.
• Compare both counters. If they are equal, return True
• Else, return False.

Output:

 The two strings are anagrams. 

Explanation:

The Counter class returns a dictionary object with each character as a key with frequency count as a value. The isAnagram() function checks whether the given strings are of the same length or not, as usual. If the strings are of different lengths, it returns False. Else, it creates two Counter objects, one for string one and another for string two. It compares both counters and returns the result.

Time Complexity - O(n): Creating a counter depends on the size of the input, which makes the time complexity of the program equal to O(n).

Space Complexity - O(n): The program creates two counters whose sizes depend on the input strings' length.

Method 4 - Using the XOR operator

The program can be summarized as follows:

• Check whether the given strings are of the same length or not. If not, then return false. If yes, follow the following steps.
• Initialize a result variable by 0.
• Concatenate both strings.
• Iterate over the characters of concatenated strings and perform bitwise XOR with the result.
• result = result^ord(character)
• Return True if result == 0, Else False.

Output:

 The two strings are anagrams. 

Explanation:

The XOR operator gives 1 when two bits are different and 0 when two bits are same.

The truth table of the XOR operator:

For example, if we XOR 10101 and 11011, we get:

10101
11011
-------
01110

In Python, the XOR operator is represented using the caret (^) symbol.

Let's take an example to understand the idea of the program.

5^3 = 6
6^3 = 5
5^5 = 0

Here, we first performed the bitwise XOR on 5 and 3. Then on 3 and 6 (the result of the previous operation). And at last, on 5 and 5 (the result of the previous operation).

The same idea works for the above program. In the above program, we first concatenated both strings using the + operator str1 + str2. Using the for loop, we have iterated over each string and performed bitwise XOR with the result. The idea is that if both strings are anagrams, the result will be 0. Else, some integer.

At the end of the program, we printed the result based on the value returned by the isAnagram function.

Time Complexity - O(n): Where n represents the size of str1+str2. A for loop is used to iterate over the concatenated string.

Space Complexity - O(1): No extra space is needed.