FAANG · LeetCode #242

Valid Anagram — three-stage drill

1The ProblemEasy

Valid Anagram

Do two strings use exactly the same letters, the same number of times?

Examples

"cat", "act"→ true"rat", "car"→ false

constraintLowercase letters; anagram = same multiset of characters.

2The PatternTIME O(n) · SPACE O(n)

Arrays & Hashing

Trade space for time: a hash map turns 'have I seen this?' into an O(1) lookup.

Problems using this pattern

3The SolutionRESULT → true

Step through it

count s: 'c' → c = 1

Step 1 / 6

Python▎count s, then subtract t

1def isAnagram(s, t):
2    if len(s) != len(t):
3        return False
4    count = {}
5    for ch in s:
6        count[ch] = count.get(ch, 0) + 1
7    for ch in t:
8        count[ch] = count.get(ch, 0) - 1
9        if count[ch] < 0:
10            return False
11    return True

why it worksAnagrams are the same multiset of letters. Tally s's letters in a count map, then subtract t's letters. If every letter cancels to zero (and none goes negative), they match — O(n) with one map instead of sorting both strings.

Arrow keys to navigate · escape to reset

All problems by pattern

Two Pointers

Sliding Window

Prefix Sum

Monotonic Deque

Shortest Subarray with Sum at Least K

Binary Search

Arrays & Hashing

Monotonic Stack

Intervals

Valid Anagram — three-stage drill

Valid Anagram

Arrays & Hashing

Step through it

All problems by pattern

Two Pointers

Sliding Window

Prefix Sum

Monotonic Deque

Binary Search

Arrays & Hashing

Monotonic Stack

Intervals

Heap / Top-K

Backtracking

Recursive Descent