Leetcode 242. Valid Anagram. DSA # 5

Question Link

Easy

Python

In this question, we have to check if the two strings are anagrams of each other or not.
Means we have to check if the two strings have the same characters or not.

Now how can we check that?

• We can sort both the strings and then compare them.

for example: s = "anagram", t = "nagaram"

After sorting: s = "aagmnr", t = "aagmnr"

Now we can compare both the strings.

But this approach will take O(nlogn) time complexity. And we don't want that

You can think like this:

• There are 26 alphabets in the English language.
• So each character of the string can be one of the 26 alphabets.
• So we can create an array of size 26 and store the count of each character in the array.
• We can store the count of any given string in the array.
• And check the other string, if we encounter 0 in the array then that means that this is the new character, then we can return False.

Let's understand it with the help of an example:

• s = "anagram", t = "nagaram"

 storage = [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]

 - We iterate over the string s and store the count of each character in the array.
    - s = "anagram"
     ---------------------------
     1. a -> storage[0] = 1
     2. n -> storage[13] = 1
     3. a -> storage[0] = 2
     4. g -> storage[6] = 1
     5. r -> storage[17] = 1
     6. a -> storage[0] = 3
     7. m -> storage[12] = 1
     ---------------------------

 storage = [3, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 1, 1, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0] 

 Now we iterate over the string t and check if we encounter 0 or not
 If we encounter 0 then that means that this character is not present in the string s.

    - t = "nagaram"
     ---------------------------
     1. n -> storage[13] = 1  Since n is present we subtract 1 from storage[13] = 0
     2. a -> storage[0] = 3   Since a is present we subtract 1 from storage[0] = 2
     3. g -> storage[6] = 1   Since g is present we subtract 1 from storage[6] = 0
     4. a -> storage[0] = 2   Since a is present we subtract 1 from storage[0] = 1
     5. r -> storage[17] = 1  Since r is present we subtract 1 from storage[17] = 0
     6. a -> storage[0] = 1   Since a is present we subtract 1 from storage[0] = 0
     7. m -> storage[12] = 1  Since m is present we subtract 1 from storage[12] = 0      
     ---------------------------     

     Since we don't encounter 0 in the array, we can return True.

     Let's take another example:

     s = "abbcc", t = "abbccc"

        storage = [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]

        - s = "abbcc"
         ---------------------------
         1. a -> storage[0] = 1
         2. b -> storage[1] = 1
         3. b -> storage[1] = 2
         4. c -> storage[2] = 1
         5. c -> storage[2] = 2
         ---------------------------

        storage = [1, 2, 2, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]

        - t = "abbccc"
         ----------------
            1. a -> storage[0] = 1  Since a is present we subtract 1 from storage[0] = 0
            2. b -> storage[1] = 2  Since b is present we subtract 1 from storage[1] = 1
            3. b -> storage[1] = 1  Since b is present we subtract 1 from storage[1] = 0
            4. c -> storage[2] = 2  Since c is present we subtract 1 from storage[2] = 1
            5. c -> storage[2] = 1  Since c is present we subtract 1 from storage[2] = 0
            6. c -> storage[2] = 0  Sice we encounter 0 in the array, we can return False.

            ---------------------------

Let's implement it:

def isAnagram(s: str, t: str) -> bool:
    s_length, t_length = len(s), len(t)
    if s_length != t_length:
        return False

    storage = [0] * 26

    for char in s:
        storage[ord(char) - ord('a')] += 1

    for char in t:
        if storage[ord(char) - ord('a')] == 0:
            return False
        storage[ord(char) - ord('a')] -= 1

    return True

Time Complexity: O(n)
Space Complexity: O(26) = O(1)

Instead of using an array of size 26, we can use a dictionary to store the count of each character.

def isAnagram(self, s: str, t: str) -> bool:
    s_length, t_length = len(s), len(t)
    if s_length != t_length:
        return False

    storage = {}

    for char in s:
        storage[char] = storage.get(char, 0) + 1

    for char in t:
        if char not in storage or storage[char] == 0:
            return False
        storage[char] -= 1

    return True