Loading…

easyStringsLC #242Frequently asked

Valid Anagram

Q: How do you solve Valid Anagram using the Sort Both Strings approach?

When to use it: The simplest correct answer — good to state first, then offer the linear counter. Anagrams become identical once their letters are sorted into canonical order. So sort `s`, sort `t`, and check the two sorted forms are equal. A length mismatch makes them unequal automatically, but checking length first is a cheaper early exit. **Why it works.** Sorting maps every permutation of the same multiset to the same string. Two strings share that canonical form exactly when they're anagrams. It's the easiest solution to get right under pressure. Time complexity: O(n log n). Space complexity: O(n).

Q: How do you solve Valid Anagram using the Frequency Count — One Counter (Optimal) approach?

When to use it: The answer they want. Phrase it as 'increment for s, decrement for t, expect all zeros'. After the length check, walk `s` incrementing a count per character, then walk `t` decrementing the same counts. If `t` is an anagram, every increment is matched by a decrement and all counts end at zero. For a 26-letter alphabet, the counter is a fixed `int[26]` indexed by `c - 'a'` — constant space and great cache behavior. **Why one counter, not two.** Building two maps and comparing them works but doubles the memory and adds a comparison pass. Incrementing then decrementing in a single table collapses the comparison into 'is everything zero?'. You can even bail early inside the second loop the moment a count dips below zero. Time complexity: O(n). Space complexity: O(1).

LCPractice

Arrays & Hashing · 2 of 83 · 6 min

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

An anagram is a word formed by rearranging the letters of another, using all the original letters exactly once.

In plain English

Decide whether `t` is just `s` with its letters shuffled. That's true exactly when both strings contain the same letters with the same multiplicities — i.e. identical character frequency tables.

Examples

Example 1

Input: s = "anagram", t = "nagaram"
Output: true
Note: Both have a×3, n×1, g×1, r×1, m×1.

Example 2

Input: s = "rat", t = "car"
Output: false
Note: s has a 't', t has a 'c' — frequencies differ.

Example 3

Input: s = "a", t = "ab"
Output: false
Note: Different lengths can never be anagrams.

Constraints

1 ≤ s.length, t.length ≤ 5 × 10⁴
s and t consist of lowercase English letters
Follow-up: what if the inputs contain Unicode characters?

Clarifying questions4First question: Is the comparison case-sensitive?Explore questions

Q1.Is the comparison case-sensitive?
Per constraints, both are lowercase, so yes treat them as-is. If mixed case, normalize first or count case separately.
Q2.What characters can appear — just a–z, or Unicode?
Constraints say lowercase English (26 letters), so a fixed array works. The follow-up asks about Unicode, where a hash map is required.
Q3.Do whitespace and punctuation count?
Not in this version. If they did, you'd decide whether to strip them before counting.
Q4.Can the strings differ in length?
Yes, and if they do the answer is immediately false — that's the first check.

Quick interview revision

Understand

30-second explanation

Build the interview-ready mental model before comparing implementations.

Two strings are anagrams iff they have identical character counts. Fast-fail on differing lengths, then count characters of one string and decrement with the other — if every count returns to zero, it's an anagram. O(n) time, O(1) space for a fixed alphabet. Sorting both strings and comparing is the simpler O(n log n) fallback.

Interview contextWhat is testedWhere candidates slipHow to stand outExplore interview context

What's being tested

Whether you model 'anagram' as a frequency-count equality and pick a fixed array over a hash map when the alphabet is small.

Where candidates slip

Skipping the length check, or assuming ASCII when the interviewer slips in 'what about Unicode?'.

How to stand out

Use a single counter (increment then decrement), state the O(1)-space claim depends on a bounded alphabet, and pivot cleanly to a hash map for Unicode.

Choose

Compare the available approaches

Use constraints and trade-offs to select the route you can defend in an interview.

Approaches at a glanceCompare before you dive in

#	Approach	Time	Space	When to mention	Jump
1	Sort Both Strings	`O(n log n)`	`O(n)`	The simplest correct answer — good to state first, then offer the linear counter.	Read
2	Frequency Count — One Counter (Optimal)Optimal	`O(n)`	`O(1)`	The answer they want. Phrase it as 'increment for s, decrement for t, expect all zeros'.	Read

Interactive decision treeInteractiveChoose the right approachFollow the branches and learn why each constraint changes the solution.First decision previewIs t an anagram of s?Lengths equal?NoYesExplore the full tree

Learn & trace

Build each solution step by step

Move from the core idea to a visual trace, implementation, proof, and edge cases.

03.1

Approach 1 of 2

Sort Both Strings

TimeO(n log n)SpaceO(n)

The simplest correct answer — good to state first, then offer the linear counter.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

If two strings are anagrams, what happens when you sort each of them?

2Hint 2Explore hint

Sort the characters of both strings and compare the results for equality.

3Hint 3Explore hint

It's correct and tiny, but sorting costs O(n log n) — beatable with counting.

A · Core idea

Anagrams become identical once their letters are sorted into canonical order. So sort s, sort t, and check the two sorted forms are equal. A length mismatch makes them unequal automatically, but checking length first is a cheaper early exit.

Why it works. Sorting maps every permutation of the same multiset to the same string. Two strings share that canonical form exactly when they're anagrams. It's the easiest solution to get right under pressure.

B · Visual dry run

Interactive dry run

Select a frame to connect the decision with its visual state.

s = "rat", t = "car"

sort s

"rat" → "art"

States' = art

Final resultfalse

C · Code with teaching comments

Reference implementation previewpublic boolean isAnagram(String s, String t) { if (s.length() != t.length()) return false; char[] a = s.toCharArray(); char[] b = t.toCharArray(); Arrays.sort(a);Explore the full code

solution.javaJava

Sort Both Strings — reference

2 teaching notes

1
public boolean isAnagram(String s, String t) {
2
    // Different lengths can't be anagrams — cheap early exit.
3
    if (s.length() != t.length()) return false;
4
    char[] a = s.toCharArray();
5
    char[] b = t.toCharArray();
6
    Arrays.sort(a);
7
    Arrays.sort(b);
8
    // Sorted forms are equal iff the originals are anagrams.
9
    return Arrays.equals(a, b);
10
}

Yellow row = the algorithm's core logic. Amber `//` lines above it = what you'd say out loud.10 lines

D · Why it works and complexityO(n log n) timeO(n) spaceOpen the invariant and proofExplore the proof

Sorting is the universal 'canonicalize then compare' trick — the same idea keys Group Anagrams. The downside is the log factor; counting removes it.

ComplexityO(n log n) time, O(n) space — Sorting dominates at O(n log n); the comparison is O(n). Space is O(n) for the sorted copies (Java char arrays / Python lists).

E · Edge cases and pitfalls2Skipping the length check and relying only on equality (still correct, just slightly slower to fail).Explore edge cases

Pitfalls

Skipping the length check and relying only on equality (still correct, just slightly slower to fail).
Forgetting sorting allocates O(n) extra space.

03.2

Approach 2 of 2 · Optimal

Frequency Count — One Counter (Optimal)

TimeO(n)SpaceO(1)

The answer they want. Phrase it as 'increment for s, decrement for t, expect all zeros'.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

Anagrams have identical letter counts. How could you compare counts without sorting?

2Hint 2Explore hint

Build a frequency table from s, then subtract t's letters from it.

3Hint 3Explore hint

If any count goes negative (or isn't zero at the end), they aren't anagrams. With 26 letters the table is a fixed-size array → O(1) space.

A · Core idea

After the length check, walk s incrementing a count per character, then walk t decrementing the same counts. If t is an anagram, every increment is matched by a decrement and all counts end at zero. For a 26-letter alphabet, the counter is a fixed int[26] indexed by c - 'a' — constant space and great cache behavior.

Why one counter, not two. Building two maps and comparing them works but doubles the memory and adds a comparison pass. Incrementing then decrementing in a single table collapses the comparison into 'is everything zero?'. You can even bail early inside the second loop the moment a count dips below zero.

B · Visual dry run

Interactive dry run

Select a frame to connect the decision with its visual state.

s = "aab", t = "aba"

Hash-map state

count s

ValueIndex / state

a→ 2

b→ 1

Continue scanning

build {a:2, b:1}

Final resulttrue

C · Code with teaching comments

solution.javaJava

Frequency Count — One Counter (Optimal) — optimal

4 teaching notes

1
public boolean isAnagram(String s, String t) {
2
    // Unequal lengths short-circuit before allocating the counter.
3
    if (s.length() != t.length()) return false;
4
    int[] count = new int[26];
5
    for (int i = 0; i < s.length(); i++) {
6
        // 'a'-offset maps a..z to 0..25; increment for s.
7
        count[s.charAt(i) - 'a']++;
8
        // Decrement for t in the SAME pass — net zero means balanced.
9
        count[t.charAt(i) - 'a']--;
10
    }
11
    for (int c : count) {
12
        // Any non-zero slot means the letter counts didn't match.
13
        if (c != 0) return false;
14
    }
15
    return true;
16
}

Yellow row = the algorithm's core logic. Amber `//` lines above it = what you'd say out loud.16 lines

D · Why it works and complexityO(n) timeO(1) spaceOpen the invariant and proofExplore the proof

A frequency array is a histogram of the string. Anagram-ness is just histogram equality, and subtracting one histogram from another and checking for all-zero is the cleanest way to assert that. This exact histogram-compare powers Permutation in String and Find All Anagrams.

ComplexityO(n) time, O(1) space — Two linear passes over the strings and one over the 26-slot table = O(n). The table size is bounded by the alphabet, so space is O(1) for lowercase English.

E · Edge cases and pitfalls5s = "", t = "" — Equal length 0, no characters to count, all-zero table → true (empty strings are anagrams).Explore edge cases

Edge cases handled

s = "", t = ""Equal length 0, no characters to count, all-zero table → true (empty strings are anagrams).
Unicode inputsSwitch the int[26] to a HashMap<Character,Integer> keyed by code point; the increment/decrement logic is unchanged.

Pitfalls

Using int[26] for Unicode — index out of bounds or wrong results; use a map.
Forgetting the length check, then the counter can falsely balance for prefixes.
Comparing two separate maps instead of one signed counter — works but more code and memory.

Practice

Try the solution yourself

Edit the optimal implementation, test another input, and observe the result.

Editable code previewpublic boolean isAnagram(String s, String t) { if (s.length() != t.length()) return false; int[] count = new int[26]; for (int i = 0; i < s.length(); i++) { count[s.charAt(i) - 'a']++;Explore the playground

Try it — Java· run a complete program; method snippets need a driver

Avoid mistakes

Recognize the interview traps

Understand why common attempts fail before reviewing the corrected implementation.

Hardcoding the 26-letter alphabet for Unicode

An int[26] indexed by c - 'a' breaks the moment a character falls outside a–z (negative index or overflow). For arbitrary characters, key a hash map by the character itself.

Explore the code comparison

Don't write this

int[] count = new int[26];
count[c - 'a']++; // crashes / wrong for non a-z

Write this instead

Map<Character, Integer> count = new HashMap<>();
count.merge(c, 1, Integer::sum);

Truthiness check that misses zero counts

In Python, checking `if count.get(c)` treats a legitimately-zero count as falsy. Always compare counts explicitly or verify all values equal zero.

Explore the code comparison

Don't write this

return not any(count.values())  # ok, but reads as 'no truthy', confusing

Write this instead

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

Revise

Carry the pattern into the interview

Quick interview revision

Pattern to remember

Character frequency match via counting

Code pattern to memorize

if len(s) != len(t): return False
count = {}
for c in s: count[c] += 1
for c in t: count[c] -= 1
return all(v == 0 for v in count.values())

Rules to remember

1Length check first — different lengths can never be anagrams, and it's a free O(1) exit.
2Increment for s, decrement for t over one map — cleaner than building two maps and comparing.
3A fixed 26-slot array beats a hash map for lowercase English — O(1) space and faster constants.
4For Unicode / arbitrary characters, use a hash map keyed by the code point, not a 26-array.
5Sorting both strings is the easy answer to fall back on, but say it's O(n log n) vs the O(n) counter.

Use this pattern when

Compare two strings for identical multiset of characters
Detect rearrangements / permutations of a word
Any 'same letters, different order' framing

Choose another pattern when

Need to group many anagrams together → sort-key the words (Group Anagrams)
Order matters, not just multiset → direct equality or sequence comparison
Streaming / sliding comparison → fixed-window frequency (Permutation in String)

Interview takeaway

Anagram = equal character histograms. The counting array is the building block for Group Anagrams, Permutation in String, and Minimum Window Substring — all of which compare frequency maps.

Continue

Transfer the pattern to another problem

Use a direct variation or pattern sibling to prove the idea is reusable.

Transferable patternCharacter-frequency comparison. Reach for it whenever two strings must match as multisets of characters. The counting table is the seed of Group Anagrams, Permutation in String, and the sliding-window anagram problems.

Practice queueDirect variations and pattern siblings

Direct follow-ups

Group Anagrams
Bucket words by their canonical (sorted or count-tuple) key.
Permutation in String
Sliding window comparing a fixed-size frequency table.
Find All Anagrams in a String
Coming soon
Same window-frequency idea, collecting every matching start index.

Same pattern

←

Two Sum

Continue · Next problem

Contains Duplicate

easyStringsLC #242Frequently asked

Valid Anagram

LCPractice

Arrays & Hashing · 2 of 83 · 6 min

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

An anagram is a word formed by rearranging the letters of another, using all the original letters exactly once.

In plain English

Decide whether `t` is just `s` with its letters shuffled. That's true exactly when both strings contain the same letters with the same multiplicities — i.e. identical character frequency tables.

Examples

Example 1

Input: s = "anagram", t = "nagaram"
Output: true
Note: Both have a×3, n×1, g×1, r×1, m×1.

Example 2

Input: s = "rat", t = "car"
Output: false
Note: s has a 't', t has a 'c' — frequencies differ.

Example 3

Input: s = "a", t = "ab"
Output: false
Note: Different lengths can never be anagrams.

Constraints

1 ≤ s.length, t.length ≤ 5 × 10⁴
s and t consist of lowercase English letters
Follow-up: what if the inputs contain Unicode characters?

Clarifying questions4First question: Is the comparison case-sensitive?Explore questions

Q1.Is the comparison case-sensitive?
Per constraints, both are lowercase, so yes treat them as-is. If mixed case, normalize first or count case separately.
Q2.What characters can appear — just a–z, or Unicode?
Constraints say lowercase English (26 letters), so a fixed array works. The follow-up asks about Unicode, where a hash map is required.
Q3.Do whitespace and punctuation count?
Not in this version. If they did, you'd decide whether to strip them before counting.
Q4.Can the strings differ in length?
Yes, and if they do the answer is immediately false — that's the first check.

Quick interview revision

Understand

30-second explanation

Build the interview-ready mental model before comparing implementations.

Interview contextWhat is testedWhere candidates slipHow to stand outExplore interview context

What's being tested

Whether you model 'anagram' as a frequency-count equality and pick a fixed array over a hash map when the alphabet is small.

Where candidates slip

Skipping the length check, or assuming ASCII when the interviewer slips in 'what about Unicode?'.

How to stand out

Use a single counter (increment then decrement), state the O(1)-space claim depends on a bounded alphabet, and pivot cleanly to a hash map for Unicode.

Choose

Compare the available approaches

Use constraints and trade-offs to select the route you can defend in an interview.

Approaches at a glanceCompare before you dive in

#	Approach	Time	Space	When to mention	Jump
1	Sort Both Strings	`O(n log n)`	`O(n)`	The simplest correct answer — good to state first, then offer the linear counter.	Read
2	Frequency Count — One Counter (Optimal)Optimal	`O(n)`	`O(1)`	The answer they want. Phrase it as 'increment for s, decrement for t, expect all zeros'.	Read

Learn & trace

Build each solution step by step

Move from the core idea to a visual trace, implementation, proof, and edge cases.

03.1

Approach 1 of 2

Sort Both Strings

TimeO(n log n)SpaceO(n)

The simplest correct answer — good to state first, then offer the linear counter.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

If two strings are anagrams, what happens when you sort each of them?

2Hint 2Explore hint

Sort the characters of both strings and compare the results for equality.

3Hint 3Explore hint

It's correct and tiny, but sorting costs O(n log n) — beatable with counting.

A · Core idea

B · Visual dry run

Interactive dry run

Select a frame to connect the decision with its visual state.

s = "rat", t = "car"

sort s

"rat" → "art"

States' = art

Final resultfalse

C · Code with teaching comments

solution.javaJava

Sort Both Strings — reference

2 teaching notes

1
public boolean isAnagram(String s, String t) {
2
    // Different lengths can't be anagrams — cheap early exit.
3
    if (s.length() != t.length()) return false;
4
    char[] a = s.toCharArray();
5
    char[] b = t.toCharArray();
6
    Arrays.sort(a);
7
    Arrays.sort(b);
8
    // Sorted forms are equal iff the originals are anagrams.
9
    return Arrays.equals(a, b);
10
}

Yellow row = the algorithm's core logic. Amber `//` lines above it = what you'd say out loud.10 lines

D · Why it works and complexityO(n log n) timeO(n) spaceOpen the invariant and proofExplore the proof

Sorting is the universal 'canonicalize then compare' trick — the same idea keys Group Anagrams. The downside is the log factor; counting removes it.

ComplexityO(n log n) time, O(n) space — Sorting dominates at O(n log n); the comparison is O(n). Space is O(n) for the sorted copies (Java char arrays / Python lists).

E · Edge cases and pitfalls2Skipping the length check and relying only on equality (still correct, just slightly slower to fail).Explore edge cases

Pitfalls

Skipping the length check and relying only on equality (still correct, just slightly slower to fail).
Forgetting sorting allocates O(n) extra space.

03.2

Approach 2 of 2 · Optimal

Frequency Count — One Counter (Optimal)

TimeO(n)SpaceO(1)

The answer they want. Phrase it as 'increment for s, decrement for t, expect all zeros'.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

Anagrams have identical letter counts. How could you compare counts without sorting?

2Hint 2Explore hint

Build a frequency table from s, then subtract t's letters from it.

3Hint 3Explore hint

If any count goes negative (or isn't zero at the end), they aren't anagrams. With 26 letters the table is a fixed-size array → O(1) space.

A · Core idea

B · Visual dry run

Interactive dry run

Select a frame to connect the decision with its visual state.

s = "aab", t = "aba"

Hash-map state

count s

ValueIndex / state

a→ 2

b→ 1

Continue scanning

build {a:2, b:1}

Final resulttrue

C · Code with teaching comments

solution.javaJava

Frequency Count — One Counter (Optimal) — optimal

4 teaching notes

1
public boolean isAnagram(String s, String t) {
2
    // Unequal lengths short-circuit before allocating the counter.
3
    if (s.length() != t.length()) return false;
4
    int[] count = new int[26];
5
    for (int i = 0; i < s.length(); i++) {
6
        // 'a'-offset maps a..z to 0..25; increment for s.
7
        count[s.charAt(i) - 'a']++;
8
        // Decrement for t in the SAME pass — net zero means balanced.
9
        count[t.charAt(i) - 'a']--;
10
    }
11
    for (int c : count) {
12
        // Any non-zero slot means the letter counts didn't match.
13
        if (c != 0) return false;
14
    }
15
    return true;
16
}

Yellow row = the algorithm's core logic. Amber `//` lines above it = what you'd say out loud.16 lines

D · Why it works and complexityO(n) timeO(1) spaceOpen the invariant and proofExplore the proof

ComplexityO(n) time, O(1) space — Two linear passes over the strings and one over the 26-slot table = O(n). The table size is bounded by the alphabet, so space is O(1) for lowercase English.

E · Edge cases and pitfalls5s = "", t = "" — Equal length 0, no characters to count, all-zero table → true (empty strings are anagrams).Explore edge cases

Edge cases handled

s = "", t = ""Equal length 0, no characters to count, all-zero table → true (empty strings are anagrams).
Unicode inputsSwitch the int[26] to a HashMap<Character,Integer> keyed by code point; the increment/decrement logic is unchanged.

Pitfalls

Using int[26] for Unicode — index out of bounds or wrong results; use a map.
Forgetting the length check, then the counter can falsely balance for prefixes.
Comparing two separate maps instead of one signed counter — works but more code and memory.

Practice

Try the solution yourself

Edit the optimal implementation, test another input, and observe the result.

Try it — Java· run a complete program; method snippets need a driver

Avoid mistakes

Recognize the interview traps

Understand why common attempts fail before reviewing the corrected implementation.

Hardcoding the 26-letter alphabet for Unicode

An int[26] indexed by c - 'a' breaks the moment a character falls outside a–z (negative index or overflow). For arbitrary characters, key a hash map by the character itself.

Explore the code comparison

Don't write this

int[] count = new int[26];
count[c - 'a']++; // crashes / wrong for non a-z

Write this instead

Map<Character, Integer> count = new HashMap<>();
count.merge(c, 1, Integer::sum);

Truthiness check that misses zero counts

In Python, checking `if count.get(c)` treats a legitimately-zero count as falsy. Always compare counts explicitly or verify all values equal zero.

Explore the code comparison

Don't write this

return not any(count.values())  # ok, but reads as 'no truthy', confusing

Write this instead

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

Revise

Carry the pattern into the interview

Quick interview revision

Pattern to remember

Character frequency match via counting

Code pattern to memorize

if len(s) != len(t): return False
count = {}
for c in s: count[c] += 1
for c in t: count[c] -= 1
return all(v == 0 for v in count.values())

Rules to remember

1Length check first — different lengths can never be anagrams, and it's a free O(1) exit.
2Increment for s, decrement for t over one map — cleaner than building two maps and comparing.
3A fixed 26-slot array beats a hash map for lowercase English — O(1) space and faster constants.
4For Unicode / arbitrary characters, use a hash map keyed by the code point, not a 26-array.
5Sorting both strings is the easy answer to fall back on, but say it's O(n log n) vs the O(n) counter.

Use this pattern when

Compare two strings for identical multiset of characters
Detect rearrangements / permutations of a word
Any 'same letters, different order' framing

Choose another pattern when

Need to group many anagrams together → sort-key the words (Group Anagrams)
Order matters, not just multiset → direct equality or sequence comparison
Streaming / sliding comparison → fixed-window frequency (Permutation in String)

Interview takeaway

Anagram = equal character histograms. The counting array is the building block for Group Anagrams, Permutation in String, and Minimum Window Substring — all of which compare frequency maps.

Continue

Transfer the pattern to another problem

Use a direct variation or pattern sibling to prove the idea is reusable.

Practice queueDirect variations and pattern siblings

Direct follow-ups

Group Anagrams
Bucket words by their canonical (sorted or count-tuple) key.
Permutation in String
Sliding window comparing a fixed-size frequency table.
Find All Anagrams in a String
Coming soon
Same window-frequency idea, collecting every matching start index.

Same pattern

←

Two Sum

Continue · Next problem

Contains Duplicate