Valid Anagram

This article will highlight two approaches to this problem

Question

Leetcode link -> https://leetcode.com/problems/valid-anagram/description/

Given two strings s and t, return true if t is an anagram of s, and false otherwise.

An Anagram is a word or phrase formed by rearranging the letters of a different word or phrase,
typically using all the original letters exactly once.

Example 1:

Input: s = "anagram", t = "nagaram"
Output: true


Example 2:

Input: s = "rat", t = "car"
Output: false


Constraints:

1 <= s.length, t.length <= 5 * 104
s and t consist of lowercase English letters.

Two approaches

• For both approaches if the length of both strings is not equal return False

1. Using Counters

• Create two counters for each string
• loop through each string counting the number of occurrences for each character
• Compare the two counters and return the boolean output

Complexity

Time

𝑂(𝑛)

• loop the two string (s and t) = 𝑂(𝑛) + 𝑂(𝑛)
• insertion into dict counters = 𝑂(1) + 𝑂(1)
• compare dicts = 𝑂(1)

2𝑂(𝑛) + 3𝑂(1) = 𝑂(𝑛)

Space

𝑂(1)

• 2 counters = 𝑂(1) + 𝑂(1)

2𝑂(1)

Code

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

        s_counter = {}
        t_counter = {}

        for char in s:
            if char in s_counter:
                s_counter[char] += 1
            else:
                s_counter[char] = 1

        for char in t:
            if char in t_counter:
                t_counter[char] += 1
            else:
                t_counter[char] = 1

        return s_counter == t_counter

2. Using inbuilt sort method

• Use python's inbuilt sorted() method for each string
• Compare if the two sorted strings are equal

Complexity

Time

𝑂(𝑛 log 𝑛 )

• The python's sorted() function uses a Timsort algorithm = 𝑂(𝑛 log 𝑛 ) + 𝑂(𝑛 log 𝑛 )
• compare the two strings = 𝑂(𝑛)

2𝑂(𝑛 log 𝑛 ) + 𝑂(𝑛) = 𝑂(𝑛 log 𝑛 )

Space

𝑂(𝑛)

• Sort function will create a new sorted string from the input string = 𝑂(𝑛) + 𝑂(𝑛)
• compare the two strings = 𝑂(𝑛)

3𝑂(𝑛) = 𝑂(𝑛)

Code

class Solution:
    def isAnagram(self, s: str, t: str) -> bool:
        if len(s) != len(t):
            return False
        return sorted(s) == sorted(t)