242. Easy

Valid Anagram🔗

EasyHash TableStringSorting·GoogleAmazon

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 * 10⁴
s and t consist of lowercase English letters.

Optimal Approach — Hash Map (Frequency Counter)

O(s+t) Time

🧮

Single Frequency Map

Time O(s+t)Space O(1)*

Instead of mapping both strings, we can map character frequencies for s, and then decrement frequencies for t.

1Check if lengths match. If not, return False immediately.
2Iterate over s and tally each character in a frequency map.
3Iterate over t, subtracting from the same frequency map.
4If any count drops below 0, it means t has more of a character than s. Return False.
5If we finish examining t without going below 0, they are PERFECT anagrams.

*Space complexity is O(1) because the size of the dictionary is bounded by 26 lowercase English letters.

String: s

String: t

HashMap { char → count }

READYPress ▶ or step forward to begin.

✓

—

String s

String t

Executing Code

def isAnagram(s, t):

    if len(s) != len(t):

        return False

    count = { }

    for char in s:

        count[char] = count.get(char, 0) + 1

    for char in t:

        count[char] = count.get(char, 0) - 1

        if count[char] < 0:

            return False

    return True

Discussion

…

Loading comments…

LeetMotion