Anagram Efficient Code

In this class, We discuss Anagram Efficient Code.

The reader can take a complete competitive coding course. Click Here.

Question:

Given two strings, a and b.

Check the two strings are an anagram of each other.

Anagram Means:

Both strings contain the same characters.

The order of the characters may change.

Example:

a = listen

b = silent

Example 2:

a = all

b = lal

Both strings contain the same characters and the same frequency of the characters.

Input: listen, silent

Output: Yes

Time complexity: O(|a| + |b|)

Space complexity: O(1)

Logic:

First way:

Take each character from the first string and count the occurrence of the characters.

The same count should be repeated in the second string.

The above approach will take O(n^2) time.

In order to maintain the time complexity of O(|a| + |b|)

We go with the second approach.

Second way:

Take two arrays of size 256.

We maintain each character’s count in the array string using ASCII values.

Suppose both arrays contain the same count. We say it as an anagram.

A step-by-step explanation of the logic is provided in the video.

Code:

class Solution:

    def isAnagram(self,a,b):

        count1 = [0] * 256

        count2 = [0] * 256

        for i in a:

            count1[ord(i)] += 1

        for i in b:

            count2[ord(i)] += 1

        if len(a) != len(b):

            return 0

        for i in range(256):

            if count1[i] != count2[i]:

                return 0

        return 1

a = input()

b=input()

ob = Solution()

j = ob.isAnagram(a,b)

if(j):

    print(“YES”)

else:

    print(“NO”)