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)