Valid Anagram: practice | DSA Trainer

1. Understand the problem

Problem statement

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

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.

Quick check

Before any hints, take a guess.

"rat" and "tar" are anagrams. "rat" and "car" are not — "car" has a 'c' and no 't'. What structure captures whether two strings have the same characters in the same amounts?

Pick an answer to continue

2. Spot the pattern

Before any code, every problem starts with a question. For this problem:

“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.

Why not Set?

A Set records which characters appeared, not how many times. Two words can share the same characters in different amounts, you need counts, not just presence.

3. 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)

Quick check

s = "abc", t = "ab". Before building any frequency map, what single check lets you return false immediately?

Pick an answer to continue

4. Climb the hint ladder

Five rungs. Click for the next one only when you genuinely need it. Each rung is a stronger nudge than the last.

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())

Quick check

s = "abc", t = "abz". After processing s, the map is {a:1, b:1, c:1}. You process t: a goes to 0, b goes to 0, then you hit 'z'. count['z'] drops to -1.

What does a negative count mean?

Pick an answer to continue

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.

Quick check

You've processed both strings and every value in the frequency map is exactly 0. Why does that prove they're anagrams?

Pick an answer to continue

7. The code

You've seen the pseudocode and the dry run. Try writing the solution yourself in the editor on the right. Run your tests there first. The reveal stays here when you're ready to check.

8. Review & common mistakes

Lock it in

What is the signal that tells you to use the Frequency Map pattern? Write it in one sentence, in your own words.

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.

Pattern family