Here, we’ll be discussing a very interesting topic the **anagram program in Python**. This is a hot topic as many questions have been asked in interviews and competitive programming sites. The topic has many variations but before you dive into its variations, you must have the basic knowledge about anagrams.

So, without wasting time, let’s start.

*What is anagram?*

*What is anagram?*

Anagram is a word or phrase that can be formed by rearranging the letters in any random order. It is also known as subsequence of a given word.

Some examples of anagram:

- School master = The classroom
- The eyes = They see

*Problem statement :-*

*Problem statement :-*

Given two strings check whether they are ** anagram program in python** of each other. If the strings are anagrams then print “Anagram” else “Not Anagram”.

DON’T PRINT INVERTED COMMAS !!

*example 1) *

string 1 = “ABC”

string 2 = “BCA”

output = Anagram

*example 2) *

string 1 = “ABC”

string 2 = “ACA”

output = Not Anagram

**Solution**

**Solution**

**Method 1(sorting): **

**Method 1(sorting):**

- Sort the Strings
- Compare the Strings

** Note:** If we found any non matching character we will print “Not Anagram” and will stop the traversal but if we have exhausted the length of the strings then it means the strings are anagrams.

*example 1)*

string 1 = “AEDBC”

string 2 = “BCDAE”

*sorting the strings*

string 1 = “ABCDE”, string 2 = “ABCDE”. So now if we compare we will conclude that both strings are anagrams.

*Program*

*Program*

```
#function defination and declaration
def areAnagram(string1, string2):
len1 = len(string1)
len2 = len(string2)
#Check if the lengths are same or not
if len1 != len2:
print("Not Anagram")
#Sorting the strings
string1 = sorted(string1)
string2 = sorted(string2)
#Comparing the strings
for itr in range(0,len1):
if string1[itr] != string2[itr]:
print("Not Anagram")
return
print("Anagram")
return
#driver code
str1 = "geekstocode"
str2 = "codegeeksto"
#function call
areAnagram(str1, str2)
```

*Code explanation: *

*Code explanation:*

- We have taken two hard-code values
and*str1*to explain the solution.*str2* - Here we pass the strings in a function called
. It takes two strings as parameter.*areAnagram* - The function first compare the length of the two strings. If the length of two strings do not match then the strings cannot be anagrams.
- Now, it will
the strings. We can use any sorting algorithm like Quick Sort, Merge Sort to sort the strings for now we have used the built in function i.e*sort*to sort the strings.*sorted(string)* - It has used a for loop to traverse the strings. Since we are comparing both strings’ index values therefore we used
**range()**. - While comparing the strings if it finds an unmatched value it print “Not Anagram” else print “Anagram”.

*Time complexity:*

*Time complexity:*

Let N be the length of the longest string. Since we are using sorting the strings and the inbuilt sorting python function takes **O(NlogN) **time and the traversal of strings will take **O(N)**. Hence the overall complexity is **O(NlogN +N)**. Since **O(NlogN)** > **O(N)**, therefore we ignore **O(N)**. The Amortized Complexity is **O(NlogN)**.

*Space complexity:*

*Space complexity:*

Since no extra space has been taken, so the space complexity will be **O(1)**.

**Method** **2(Count Characters):**

**Method**

**2(Count Characters):**

Here we will create two 1D arrays to store the count of characters in each string and then we will compare both arrays indices value. If we found any unmatched value then we will print “Not Anagram” otherwise we will keep traversing until array got exhausted and finally print “Anagram”.

The size of the arrays will be ** 256** because there are only

**characters. Here the ASCII value of character will be considered as index of the array.**

*256 ASCII**example 1)*

String1 = “** BCDEAB**“

String2 = “** ACDBEB**“

*Program*

```
TOT_CHAR = 256
#function defination and declaration
def areAnagram(string1, string2):
#an array of zeros
len1 = len(string1)
len2 = len(string2)
count1 = [0] * TOT_CHAR
count2 = [0] * TOT_CHAR
#Check if the lengths are same or not
if len1 != len2:
print("Not Anagram")
return
#string1 will increase the frequency
#ord(char) function provides the ASCII value of the argument
for itr in string1:
count1[ord(itr)] += 1
#string2 will decrease the frequency
for itr in string2:
count2[ord(itr)] +=1
#Comparing the strings
for itr in range(TOT_CHAR):
if count1[itr] != count2[itr]:
print("Not Anagram")
return
print("Anagram")
return
#
```**driver code**
str1 = "geekstocode"
str2 = "codegeeksto"
#function call
areAnagram(str1, str2)

*Code explanation: *

*Code explanation:*

- We have taken two hard-code values
and*str1*to explain the solution.*str2* - Here we pass the strings in a function called
. It takes two strings as parameter.*are Anagram* - Inside function we have created two frequency table
and*count1**count2*. - The function first compare the length of the two strings. If the length of two strings do not match then the strings cannot be anagrams.
- Now, we traverse the
string and*first*the count of characters in count1. Similarly, we traverse the*increase*string and*second*count of characters in count2.*increase* - After we traversed both the strings, we will compare the two arrays count1 and count2, for this we have used a
. If at any index we found an*for loop*we stopped the traversal and print “Not Anagram”, otherwise we will keep on traversing and finally print “Anagram”.*unmatched value*

*Time Complexity:*

*Time Complexity:*

Since we are traversing the array only once. Therefore the run time complexity is **O(N)**, where **N** is the length of the string.

**Space Complexity:**

**Space Complexity:**

Here although we are creating two arrays or frequency tables of 256 elements that is 512 but because 512 is very small number and does not depend on any other factor, therefore it will be considered as a constant space. Hence the space complexity would be **O(1)**.

**Method 3(Count Characters Efficient Method):**

**Method 3(Count Characters Efficient Method):**

Here also we will create a frequency table but this time we don’t need two different arrays to store the count of characters. Instead, we will try to use a very simple logic to optimize the previous method. (**anagram program in python**)

**Optimized Logic**:

- Assign
to the frequency table*Zero* - Traverse first string and keep
the count of characters in the frequency table.*adding* - Now, traverse second string, here we will
the count of characters from the frequency table.*reduce*

* Note:* While reducing the frequency if we encounter an index where the frequency is

**so we will print “Not anagram” and stop the traversal. Otherwise, we will keep on traversing.**

*NIL**example 1)*

String1 = “BCDEAB”

String2 = “ACDBEB”

*Program*

*Program*

```
TOT_CHAR = 256
#function defination and declaration
def areAnagram(string1, string2):
#an array of zeros
len1 = len(string1)
len2 = len(string2)
count = [0] * 256
#Check if the lengths are same or not
if len1 != len2:
print("Not Anagram")
return
#string1 will increase the frequency
for itr in string1:
count[ord(itr)] += 1
#string2 will decrease the frequency
for itr in string2:
count[ord(itr)] -=1
#Comparing the strings
for itr in range(TOT_CHAR):
if count[itr] != 0:
print("Not Anagram")
return
print("Anagram")
return
#driver code
str1 = "geekstocode"
str2 = "codegeeksto"
#function call
areAnagram(str1, str2)
```

*Code explanation: *

*Code explanation:*

- We have taken two hard-code values
and*str1*to explain the solution.*str2* - Here we pass the strings in a function called
. It takes two strings as parameter.*are Anagram* - In previous method we have created two different frequency arrays
and*count1*. In this method we improved the solution and just created a single count array.*count2* - The function first compare the length of the two strings. If the length of two strings do not match then the strings cannot be anagrams.
- Now, we traverse the first string and
**increase**the count of characters in count array. Similarly, we traverse the second string but**decrease**the count of characters in count array. - After we traversed both the strings, we will check the count array and for this we used for loop. If at any index we found a non-zero value we stopped the traversal and print “Not Anagram”, otherwise we keep on traversing and finally print “Anagram”.

*Time Complexity:*

*Time Complexity:*

let N be the length of longest string. We are just traversing the array twice so time complexity would be **O(2N)**. Since 2 is a constant and we ignore constants while calculating time complexity. Therefore the run time complexity would be **O(N)**.

**Space Complexity:**

**Space Complexity:**

Here although we are creating an array or frequency table of 256 elements but because 256 is very small number and does not depend on any other factor, therefore it will be consider as a constant space. Hence the space complexity would be **O(1)**.

*Method 4(Summation):*

*Method 4(Summation):*

Here we will discuss an another ** optimized** solution to solve the above problem. In previous method we took an array and increment the count of characters while traversing first string and decrement the count while traversing the second string. Here we won’t be using array but we will make a use of ASCII values.

**Optimized Logic**:

- Initialize a variable
= 0.*sum* - Traverse the first string and keep
the ASCII value of the characters.*adding* - Traverse the second string and keep
the ASCII value of the characters.*subtracting* - If the final value of sum is
**not**equal to**zero**then the strings are “Not anagrams” else “Anagram”.

*example 1)*

String1 = “BCDEAB”

String2 = “ACDBEB”

*Program*

```
#function defination and declaration
def areAnagram(string1, string2):
#an array of zeros
len1 = len(string1)
len2 = len(string2)
sum = 0
#Check if the lengths are same or not
if len1 != len2:
print("Not Anagram")
return
#ord(char) function provides the ASCII value of the argument
for itr in range(len1):
sum += ord(string1[itr])
sum -= ord(string2[itr])
if(sum != 0):
print("Not Anagram")
return
print("Anagram")
return
#driver code
str1 = "geekstocode"
str2 = "codegeeksto"
#function call
areAnagram(str1, str2)
```

*Code explanation: *

*Code explanation:*

- We have taken two hard-code values
and*str1*to explain the solution.*str2* - Here we pass the strings in a function called
. It takes two strings as parameter.*areAnagram* - In previous methods we were using an extra array to store the frequency of characters to solve the problem but this method has a very unique and the optimized solution. Here we eliminate the use of extra array by the concept of summation. For this we created a
**sum**variable. - Now, we used a for loop and at every index we
the ASCII value of characters from the first string and*add*the ASCII value of characters from the second string. By this way the ASCII value of character added from first string will be subtracted from its appearance in second string if it exists in second string to nullify the effect on*subtract*variable.*sum* - After the above logic, we just need to check if if
variable has no-zero value or not. If the value is non-zero then it is “Not Anagram” else “Anagram”.*sum*

**Time Complexity:**

**Time Complexity:**

Here the strings are traversed only once therefore the run time complexity is **O(N)**.

*Space Complexity: *

*Space Complexity:*

Here we have just taken a variable to store the sum** **and we know variable takes constant space. Hence the space complexity is** ****O(1)**.

## Conclusion

We have discussed “what is anagram?”, ** anagram program in python** and we have seen a very simple application on it. Analyzed the complexity of each method. We can clearly see the method 4 is the most optimized among all other methods. The fact is anagram is not a small topic to cover it in a single article, to get a better grip on this topic we need to solve more classical problems. Here we have solved a very important and basic problem. Don’t stop here keep solving problems on anagrams. Hope you find this article on anagram program in python useful.