Anagram Program In Python | Code and Explanation

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?

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 :-

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

Method 1(sorting):

  1. Sort the Strings
  2. 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
#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)

Run Code Here

Code explanation:
  1. We have taken two hard-code values str1 and str2 to explain the solution.
  2. Here we pass the strings in a function called areAnagram. It takes two strings as parameter.
  3. 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.
  4. Now, it will sort 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 sorted(string) to sort the strings.
  5. It has used a for loop to traverse the strings. Since we are comparing both strings’ index values therefore we used range().
  6. While comparing the strings if it finds an unmatched value it print “Not Anagram” else print “Anagram”.
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:

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

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 256 ASCII characters. Here the ASCII value of character will be considered as index of the array.

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:
  1. We have taken two hard-code values str1 and str2 to explain the solution.
  2. Here we pass the strings in a function called are Anagram. It takes two strings as parameter.
  3. Inside function we have created two frequency table count1 and count2.
  4. 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.
  5. Now, we traverse the first string and increase the count of characters in count1. Similarly, we traverse the second string and increase count of characters in count2.
  6. After we traversed both the strings, we will compare the two arrays count1 and count2, for this we have used a for loop. If at any index we found an unmatched value we stopped the traversal and print “Not Anagram”, otherwise we will keep on traversing and finally print “Anagram”.
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:

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):

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:

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

Note: While reducing the frequency if we encounter an index where the frequency is NIL so we will print “Not anagram” and stop the traversal. Otherwise, we will keep on traversing.

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)
    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:
  1. We have taken two hard-code values str1 and str2 to explain the solution.
  2. Here we pass the strings in a function called are Anagram. It takes two strings as parameter.
  3. In previous method we have created two different frequency arrays count1 and count2. In this method we improved the solution and just created a single count array.
  4. 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.
  5. 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.
  6. 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:

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:

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):

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:

  1. Initialize a variable sum = 0.
  2. Traverse the first string and keep adding the ASCII value of the characters.
  3. Traverse the second string and keep subtracting the ASCII value of the characters.
  4. 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)

Run Code Here

Code explanation:
  1. We have taken two hard-code values str1 and str2 to explain the solution.
  2. Here we pass the strings in a function called areAnagram. It takes two strings as parameter.
  3. 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.
  4. 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.
  5. Now, we used a for loop and at every index we add the ASCII value of characters from the first string and subtract 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 sum variable.
  6. After the above logic, we just need to check if if sum variable has no-zero value or not. If the value is non-zero then it is “Not Anagram” else “Anagram”.
Time Complexity:

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

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.

Leave a Comment

Your email address will not be published. Required fields are marked *