Valid Anagram

PracticeNeetCode ↗LeetCode ↗

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

Example

Key Pointers

• Anagram means same characters, same counts, any order — a length mismatch is an instant "no".
• A hashmap of character → count captures s's "signature"; t must consume that signature exactly.
• Decrementing counts as you walk t (instead of building a second map and comparing at the end) lets you fail fast.

Step-by-Step Analysis

1. If len(s) != len(t), return False right away.
2. Build a count map from every character in s.
3. Walk t, decrementing the count for each character; if a character is missing from the map or its count is already 0, return False.
4. If t is fully consumed without a mismatch, return True.

Complexity

Time: O(n) — Space: O(n)

Code

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

    count = {}
    for ch in s:
        count[ch] = count.get(ch, 0) + 1

    for ch in t:
        if ch not in count or count[ch] == 0:
            return False
        count[ch] -= 1

    return True

Code Explanation

How the solution above works, piece by piece.

1. if len(s) != len(t): return False: different lengths can never be anagrams, and this check makes the later logic safe.
2. First loop: count every letter of s in a dictionary, count[ch] = count.get(ch, 0) + 1.
3. Second loop: spend those counts on the letters of t. If a letter is missing or its count is already 0, t has more of it than s → False.
4. Otherwise count[ch] -= 1.
5. If every letter of t was paid for and the lengths match, every count ends at exactly 0, so it is an anagram. O(n) time; the dictionary has at most 26 keys, so O(1) extra space.

Visual Walkthrough

Running it on s = "anagram", t = "nagaram":

Video Explanation

NeetCode — LeetCode 242