Frequency MapEasy

Valid Anagram

Frequency MapEasy

Step 1 of 8 · Understand

1. Understand the problem

Two strings are anagrams if one can be rearranged to form the other — same characters, same counts, different order. Given strings s and t, return true if t is an anagram of s.

Input

Two strings `s` and `t`, containing only lowercase English letters.

Output

A boolean — `true` if `t` is an anagram of `s`, `false` otherwise.

Examples

input → s = "anagram", t = "nagaram"

output → true

Both strings contain: a×3, n×1, g×1, r×1, m×1.

input → s = "rat", t = "car"

output → false

rat has r×1, a×1, t×1. car has c×1, a×1, r×1. The t is missing and c is extra.

1. Understand the problem

Two strings are anagrams if one can be rearranged to form the other — same characters, same counts, different order. Given strings s and t, return true if t is an anagram of s.

Input

Two strings `s` and `t`, containing only lowercase English letters.

Output

A boolean — `true` if `t` is an anagram of `s`, `false` otherwise.

Examples

input → s = "anagram", t = "nagaram"

output → true

Both strings contain: a×3, n×1, g×1, r×1, m×1.

input → s = "rat", t = "car"

output → false

rat has r×1, a×1, t×1. car has c×1, a×1, r×1. The t is missing and c is extra.

2. Brute force idea

Sort both strings alphabetically. If they're anagrams, the sorted versions will be identical — 'anagram' and 'nagaram' both sort to 'aaagmnr'.

Brute force — the slow one

O(n log n)

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

return sorted(s) == sorted(t)    # ← sorting is the expensive part

Why this is too slow

Sorting takes O(n log n) where n is the length of the string. For very long strings that's meaningful overhead — and sorting doesn't give you any insight into *which* characters differ, only whether the totals match.

Why this is not ideal for interviews

Sorting is a valid approach and worth mentioning, but most interviewers are looking for you to spot the frequency-count pattern. Counting characters is O(n) and only needs a single pass — it's the more direct solution to 'do these strings have the same character breakdown?'

Time: O(n log n)

Space: O(n)

3. Spot the pattern

Before any code, every problem starts with a question. For the Frequency Map pattern, that question is:

“Can I count how often each character appears in both strings and compare those counts?”

Whenever a problem boils down to 'do these two things have the same composition?' — same characters, same words, same elements — the answer is almost always a frequency map. Count occurrences on one side, subtract (or verify) on the other.

5. The optimized approach

If the lengths differ, return false immediately. Otherwise build a frequency map by incrementing counts for each character in s and decrementing for each character in t. If all counts end up at zero, the strings are anagrams.

Pseudocode

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

count = {}    # char -> net count

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

for c in t:
    count[c] = count.get(c, 0) - 1

return all(v == 0 for v in count.values())

6. Dry run, row by row

Trace it with the first example — s = "anagram", t = "nagaram".

step	char	from s (+1)	from t (−1)
1	a	+3	−3
2	n	+1	−1
3	g	+1	−1
4	r	+1	−1
5	m	+1	−1

step 1: 'a' appears 3 times in 'anagram' and 3 times in 'nagaram'. Net zero.

step 2: Net zero.

step 3: Net zero.

step 4: Net zero.

step 5: All counts are 0 — return true.

8. Review & common mistakes

Common mistakes

Forgetting the length check
'listen' and 'silent' are anagrams but 'abc' and 'ab' are not — they can't be if the lengths differ. A quick length comparison at the top saves you from a false positive when one string has extra characters.
Only counting characters in s, not verifying t
Counting s alone tells you what characters s has. You still need to verify that t has exactly the same counts. Decrement for t (or build a second map and compare) — don't skip the second pass.
Using sorted() and calling it the optimal solution
Sorting gets you the right answer but it's O(n log n). The counting approach is O(n). Both are worth knowing, but in an interview always explain the tradeoff and lead with the faster one.

Try next (when these problems ship)

Contains Duplicate
Two Sum

Ready to go deeper?

Unlock 10 more problems covering Sliding Window, Binary Search, Linked Lists, Trees, and more — same guided format, same hint ladder, one-time $10.

See all problems →

Write your solution above and hit Run tests. Results and tips appear here.

Valid Anagram

1. Understand the problem

1. Understand the problem

2. Brute force idea

3. Spot the pattern

4. Climb the hint ladder

5. The optimized approach

6. Dry run, row by row

7. The code

8. Review & common mistakes