Loading…

easyStringsLC #383Frequently asked

Ransom Note

Q: How do you solve Ransom Note using the Brute Force — Search and Strike Out (Don't Ship) approach?

When to use it: Mention briefly to show progression, then immediately move to counting — the O(n·m) cost is the giveaway. The most literal model is physical: hold the magazine, and for each letter of the ransom note find that letter somewhere in the magazine and cut it out so it can't be reused. **Why it is correct.** Cutting out a letter enforces the 'use each once' rule directly — a consumed character is gone for future lookups. If at any point the needed letter isn't found, the note can't be built. **Why it is slow.** Each 'find and remove' is a linear scan of the remaining magazine, and we do it once per note character. That's `O(n·m)`, which for `10⁵`-length strings is up to `10¹⁰` operations — far too slow. The repeated scanning re-examines the same characters again and again. **The fix it motivates.** All that repeated searching exists only to answer 'is there still a spare copy of this letter?'. A frequency count answers that in `O(1)` after a single pass — which is exactly the optimal approach below. Naming this brute force shows the interviewer you derived the counting solution rather than memorised it. Time complexity: O(n·m). Space complexity: O(m).

Q: How do you solve Ransom Note using the Frequency Count — int[26] / Hash Map (Optimal) approach?

When to use it: The answer they want. Phrase it as 'count the magazine's supply, then check it covers the note's demand'. The problem is pure multiset containment: can the magazine's multiset of letters cover the ransom note's multiset? That reduces to one rule — for every letter, `supply ≥ demand`. **Build the supply once.** Scan the magazine and tally each letter into a fixed `int[26]`, where `index = ch − 'a'`. Because the alphabet is a known 26 lowercase letters, the array *is* the hash map — direct indexing, no hashing, cache-friendly, and `O(1)` space (26 is a constant independent of input size). **Consume the demand in one pass.** Walk the ransom note; for each letter decrement its slot. The instant a slot goes negative, the magazine has been asked for more copies of that letter than it had — return `false` immediately (fail fast). If the whole note is processed without any slot going negative, every demand was covered → return `true`. Decrement-then-check-negative is exactly equivalent to comparing 'have ≥ need' per letter, but it short-circuits as early as possible. **Why this is not Valid Anagram.** Anagram demands the counts match *exactly* (`==`); Ransom Note only demands the supply *covers* the demand (`≥`). Leftover magazine letters are fine. Using `==` here would wrongly reject `note = "a", magazine = "ab"`. The distinction — equality vs coverage — is the conceptual trap. **Fail-fast length check.** If `ransomNote.length() > magazine.length()`, the magazine can't possibly have enough total letters, so return `false` before counting. It's a cheap optimisation that also reads as careful thinking. Time complexity: O(n + m). Space complexity: O(1).

LCPractice

Arrays & Hashing · 15 of 83 · 6 min

Given two strings ransomNote and magazine, return true if ransomNote can be constructed by using the letters from magazine, and false otherwise.

Each letter in `magazine` can only be used once in ransomNote.

In plain English

We must be able to spell out ransomNote by physically cutting letters out of the magazine, where each magazine character is consumed once. This means: for every letter, the magazine must contain at least as many copies as the ransom note requires. Position and order do not matter — only the per-letter counts.

Examples

Example 1

Input: ransomNote = "a", magazine = "b"
Output: false
Note: The magazine has no 'a' to supply the note's single required 'a'.

Example 2

Input: ransomNote = "aa", magazine = "ab"
Output: false
Note: The note needs two 'a's but the magazine supplies only one. Counts must cover, and 1 < 2.

Example 3

Input: ransomNote = "aa", magazine = "aab"
Output: true
Note: Magazine has two 'a's (and a spare 'b'); the note's demand of two 'a's is covered.

Constraints

1 ≤ ransomNote.length, magazine.length ≤ 10⁵
ransomNote and magazine consist of lowercase English letters only

Clarifying questions4First question: Can a magazine letter be reused for multiple note positions?Explore questions

Q1.Can a magazine letter be reused for multiple note positions?
No. Each magazine letter is consumed once. That's why we need counts, not just membership — three 'a's in the note require three 'a's in the magazine.
Q2.What characters can appear?
Lowercase English letters only. That lets us use a fixed-size int[26] instead of a general hash map.
Q3.Is it case-sensitive or whitespace-sensitive?
Per the constraints, only lowercase letters appear — no case-folding or whitespace handling needed here.
Q4.Does the magazine have to be fully used?
No. Leftover magazine letters are fine; we only need it to cover the note's demand.

Quick interview revision

Understand

30-second explanation

Build the interview-ready mental model before comparing implementations.

Tally the letter counts of the magazine, then verify the ransom note never demands more of any letter than the magazine supplies. Count magazine letters in a hash map (or int[26]), decrement per note letter, and return false the moment a count goes negative. O(n + m) time.

Interview contextWhat is testedWhere candidates slipHow to stand outExplore interview context

What's being tested

Whether you model 'each letter used once' as a multiset-containment check via frequency counts, and pick the O(n+m) counting solution over an O(n·m) repeated-search approach.

Where candidates slip

Using set membership (treating letters as reusable) instead of counts, or comparing counts for equality (==) as in an anagram when you only need supply ≥ demand.

How to stand out

Note the fail-fast length check, choose int[26] for the lowercase constraint, and decrement-on-the-fly returning false at the first negative — one pass after building counts.

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	Brute Force — Search and Strike Out (Don't Ship)	`O(n·m)`	`O(m)`	Mention briefly to show progression, then immediately move to counting — the O(n·m) cost is the giveaway.	Read
2	Frequency Count — int[26] / Hash Map (Optimal)Optimal	`O(n + m)`	`O(1)`	The answer they want. Phrase it as 'count the magazine's supply, then check it covers the note's demand'.	Read

Interactive decision treeInteractiveChoose the right approachFollow the branches and learn why each constraint changes the solution.First decision previewCount letters in magazine (supply)supply[letter] > 0?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

Brute Force — Search and Strike Out (Don't Ship)

TimeO(n·m)SpaceO(m)

Mention briefly to show progression, then immediately move to counting — the O(n·m) cost is the giveaway.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

Literal approach: for each letter of the note, find an unused copy in the magazine and 'cross it out'. What does 'find and remove' cost each time?

2Hint 2Explore hint

Searching the magazine for each note character and deleting it is a linear scan per character.

3Hint 3Explore hint

n note characters × O(m) search/delete each = O(n·m). Correct, but the repeated scanning is wasteful.

A · Core idea

The most literal model is physical: hold the magazine, and for each letter of the ransom note find that letter somewhere in the magazine and cut it out so it can't be reused.

Why it is correct. Cutting out a letter enforces the 'use each once' rule directly — a consumed character is gone for future lookups. If at any point the needed letter isn't found, the note can't be built.

Why it is slow. Each 'find and remove' is a linear scan of the remaining magazine, and we do it once per note character. That's O(n·m), which for 10⁵-length strings is up to 10¹⁰ operations — far too slow. The repeated scanning re-examines the same characters again and again.

The fix it motivates. All that repeated searching exists only to answer 'is there still a spare copy of this letter?'. A frequency count answers that in O(1) after a single pass — which is exactly the optimal approach below. Naming this brute force shows the interviewer you derived the counting solution rather than memorised it.

B · Visual dry run

Interactive dry run

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

ransomNote = "aa", magazine = "aab"

note 'a' (1st)

find 'a' in "aab", strike it

Statemagazine → "ab"

Final resulttrue

C · Code with teaching comments

Reference implementation previewpublic boolean canConstruct(String ransomNote, String magazine) { StringBuilder pool = new StringBuilder(magazine); for (int i = 0; i < ransomNote.length(); i++) { int idx = pool.indexOf(String.valueOf(ransomNote.charAt(i))); if (idx < 0) return false;Explore the full code

solution.javaJava

Brute Force — Search and Strike Out (Don't Ship) — reference

3 teaching notes

1
public boolean canConstruct(String ransomNote, String magazine) {
2
    StringBuilder pool = new StringBuilder(magazine);
3
    for (int i = 0; i < ransomNote.length(); i++) {
4
        // Linear search for an unused copy of this letter — the O(m) step done n times.
5
        int idx = pool.indexOf(String.valueOf(ransomNote.charAt(i)));
6
        // No copy left → the note can't be constructed.
7
        if (idx < 0) return false;
8
        // Consume the letter so it can't be reused — also O(m) due to shifting.
9
        pool.deleteCharAt(idx);
10
    }
11
    return true;
12
}

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

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

Repeatedly scanning to ask 'is there one left?' is the smell that a frequency count should replace the search. Whenever brute force re-scans for availability, precompute counts.

ComplexityO(n·m) time, O(m) space — For each of the n note characters we scan up to m magazine characters to find and remove a copy → O(n·m) time. Mutable copy of the magazine → O(m) space.

E · Edge cases and pitfalls4ransomNote = "a", magazine = "" — First lookup fails immediately → returns false.Explore edge cases

Edge cases handled

ransomNote = "a", magazine = ""First lookup fails immediately → returns false.

Pitfalls

Re-scanning the magazine for every note character — O(n·m) blows up at 10⁵.
Forgetting to remove the matched letter, which would allow illegal reuse.
Using indexOf/remove inside the loop and not realising each is itself O(m).

03.2

Approach 2 of 2 · Optimal

Frequency Count — int[26] / Hash Map (Optimal)

TimeO(n + m)SpaceO(1)

The answer they want. Phrase it as 'count the magazine's supply, then check it covers the note's demand'.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

You only ever ask 'are there enough of letter X left?'. What structure answers that in O(1) without rescanning?

2Hint 2Explore hint

Count every letter in the magazine into an int[26] (index = ch - 'a'). Then walk the note, decrementing the matching count.

3Hint 3Explore hint

If any count drops below 0, the magazine ran out of that letter → return false. Survive the whole note → return true.

A · Core idea

The problem is pure multiset containment: can the magazine's multiset of letters cover the ransom note's multiset? That reduces to one rule — for every letter, supply ≥ demand.

Build the supply once. Scan the magazine and tally each letter into a fixed int[26], where index = ch − 'a'. Because the alphabet is a known 26 lowercase letters, the array is the hash map — direct indexing, no hashing, cache-friendly, and O(1) space (26 is a constant independent of input size).

Consume the demand in one pass. Walk the ransom note; for each letter decrement its slot. The instant a slot goes negative, the magazine has been asked for more copies of that letter than it had — return false immediately (fail fast). If the whole note is processed without any slot going negative, every demand was covered → return true. Decrement-then-check-negative is exactly equivalent to comparing 'have ≥ need' per letter, but it short-circuits as early as possible.

Why this is not Valid Anagram. Anagram demands the counts match exactly (==); Ransom Note only demands the supply covers the demand (≥). Leftover magazine letters are fine. Using == here would wrongly reject note = "a", magazine = "ab". The distinction — equality vs coverage — is the conceptual trap.

Fail-fast length check. If ransomNote.length() > magazine.length(), the magazine can't possibly have enough total letters, so return false before counting. It's a cheap optimisation that also reads as careful thinking.

B · Visual dry run

Interactive dry run

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

ransomNote = "aa", magazine = "aab"

Hash-map state

magazine counted

ValueIndex / state

a→ 2

b→ 1

Match found

supply built from "aab"

Final resulttrue

C · Code with teaching comments

solution.javaJava

Frequency Count — int[26] / Hash Map (Optimal) — optimal

4 teaching notes

1
public boolean canConstruct(String ransomNote, String magazine) {
2
    // Fail fast — the magazine can't supply more letters than it has in total.
3
    if (ransomNote.length() > magazine.length()) return false;
4
    int[] counts = new int[26];
5
    for (int i = 0; i < magazine.length(); i++) {
6
        // Build the supply: char minus 'a' maps a..z to indices 0..25.
7
        counts[magazine.charAt(i) - 'a']++;
8
    }
9
    for (int i = 0; i < ransomNote.length(); i++) {
10
        // Consume a copy; a negative count means the magazine ran out of this letter.
11
        if (--counts[ransomNote.charAt(i) - 'a'] < 0) {
12
            return false;
13
        }
14
    }
15
    // Survived the whole note without exhausting any letter → constructible.
16
    return true;
17
}

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

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

Multiset containment = 'for every key, supply ≥ demand'. Count the supply, then either compare per-letter or decrement-and-watch-for-negative. Recognising the ≥ (not ==) is what separates this from Valid Anagram.

ComplexityO(n + m) time, O(1) space — One pass over the magazine (O(m)) to build counts, one pass over the note (O(n)) to consume them → O(n + m) time. The count array is a fixed 26 slots → O(1) space.

E · Edge cases and pitfalls6ransomNote = "aa", magazine = "ab" — a: 1 → 0 on first 'a', then 0 → -1 on second 'a' → returns false.Explore edge cases

Edge cases handled

ransomNote = "aa", magazine = "ab"a: 1 → 0 on first 'a', then 0 → -1 on second 'a' → returns false.
ransomNote = "a", magazine = "a"a: 1 → 0, no negative → returns true.
ransomNote = "abc", magazine = "ab"Length check: 3 > 2 → returns false immediately.

Pitfalls

Comparing counts with == (anagram logic) instead of ≥ — leftover magazine letters are allowed.
Counting the ransom note instead of the magazine and getting the direction of the check backwards.
Forgetting the negative check after decrementing — the whole correctness hinges on it.

Practice

Try the solution yourself

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

Editable code previewpublic boolean canConstruct(String ransomNote, String magazine) { if (ransomNote.length() > magazine.length()) return false; int[] counts = new int[26]; for (int i = 0; i < magazine.length(); i++) { counts[magazine.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.

Set membership instead of counts

A set ignores multiplicity, so it wrongly accepts note = "aa", magazine = "ab" (it sees 'a' exists). You must consume each letter once via counts.

Explore the code comparison

Don't write this

mag = set(magazine)
return all(ch in mag for ch in ransomNote)

Write this instead

counts = [0] * 26
for ch in magazine: counts[ord(ch) - 97] += 1
for ch in ransomNote:
    counts[ord(ch) - 97] -= 1
    if counts[ord(ch) - 97] < 0: return False
return True

Equality check (anagram confusion)

Ransom Note needs the magazine to COVER the note (supply ≥ demand), not match exactly. Comparing for equality rejects valid inputs with spare letters.

Explore the code comparison

Don't write this

from collections import Counter
return Counter(ransomNote) == Counter(magazine)

Write this instead

from collections import Counter
need, have = Counter(ransomNote), Counter(magazine)
return all(have[ch] >= cnt for ch, cnt in need.items())

Missing the negative check

Decrementing without checking for a negative count never detects exhaustion, so the function always returns true.

Explore the code comparison

Don't write this

counts[ransomNote.charAt(i) - 'a']--;
// no check, falls through to return true

Write this instead

if (--counts[ransomNote.charAt(i) - 'a'] < 0) {
    return false;
}

Revise

Carry the pattern into the interview

Quick interview revision

Pattern to remember

Frequency count + sufficiency check (counts must cover)

Code pattern to memorize

need = Counter(ransomNote)
have = Counter(magazine)
return all(have[ch] >= cnt for ch, cnt in need.items())

Rules to remember

1Each magazine letter can be used at most once → this is a multiset containment check, not a set check.
2Count the magazine (the supply), then make sure it covers every letter the note needs.
3Fail fast: if len(ransomNote) > len(magazine) it's immediately false — the note can't fit.
4Lowercase English only → an `int[26]` array beats a hash map on constant factors.
5Decrement-and-check-negative is equivalent to compare-counts; either works, but don't forget the negative check.
6Order and position are irrelevant — only multiplicities matter.

Use this pattern when

Check whether one multiset of characters can be built from another
'Can string A be formed using the letters of string B?' style prompts
Anagram / letter-availability problems with a fixed small alphabet
You need counts to cover (≥), not exactly match

Choose another pattern when

Letters can be reused unlimited times → it's a set-membership check, not counts
You must preserve order or contiguity → substring / subsequence problem
Exact equality of counts required → that's Valid Anagram, use ==
Alphabet is huge/unicode and memory is tight → hash map over fixed array

Interview takeaway

Containment of one multiset in another reduces to 'for every letter, supply ≥ demand'. Count the supply once and check coverage. The same counting skeleton solves Valid Anagram (==), Find All Anagrams (sliding window of counts), and Minimum Window Substring (cover a demand set).

Continue

Transfer the pattern to another problem

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

Transferable patternMultiset containment via frequency counting. Count the supply (magazine), then verify supply ≥ demand for every letter — either by comparison or decrement-and-check-negative. The ≥ (coverage) distinguishes it from Valid Anagram's == (equality); both share the int[26] / Counter skeleton.

Practice queueDirect variations and pattern siblings

Direct follow-ups

Valid Anagram
Same counting, but require exact equality (==) of all letter counts.
Group Anagrams
Use a frequency-derived signature as a grouping key.
Find All Anagrams in a String
Coming soon
Slide a fixed-size window and compare letter counts at each position.
Minimum Window Substring
Cover a demand multiset within a sliding window — coverage check at scale.

Same pattern

←

Repeated String

Continue · Next problem

Contains Duplicate II

easyStringsLC #383Frequently asked

Ransom Note

LCPractice

Arrays & Hashing · 15 of 83 · 6 min

Given two strings ransomNote and magazine, return true if ransomNote can be constructed by using the letters from magazine, and false otherwise.

Each letter in `magazine` can only be used once in ransomNote.

In plain English

Examples

Example 1

Input: ransomNote = "a", magazine = "b"
Output: false
Note: The magazine has no 'a' to supply the note's single required 'a'.

Example 2

Input: ransomNote = "aa", magazine = "ab"
Output: false
Note: The note needs two 'a's but the magazine supplies only one. Counts must cover, and 1 < 2.

Example 3

Input: ransomNote = "aa", magazine = "aab"
Output: true
Note: Magazine has two 'a's (and a spare 'b'); the note's demand of two 'a's is covered.

Constraints

1 ≤ ransomNote.length, magazine.length ≤ 10⁵
ransomNote and magazine consist of lowercase English letters only

Clarifying questions4First question: Can a magazine letter be reused for multiple note positions?Explore questions

Q1.Can a magazine letter be reused for multiple note positions?
No. Each magazine letter is consumed once. That's why we need counts, not just membership — three 'a's in the note require three 'a's in the magazine.
Q2.What characters can appear?
Lowercase English letters only. That lets us use a fixed-size int[26] instead of a general hash map.
Q3.Is it case-sensitive or whitespace-sensitive?
Per the constraints, only lowercase letters appear — no case-folding or whitespace handling needed here.
Q4.Does the magazine have to be fully used?
No. Leftover magazine letters are fine; we only need it to cover the note's demand.

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 'each letter used once' as a multiset-containment check via frequency counts, and pick the O(n+m) counting solution over an O(n·m) repeated-search approach.

Where candidates slip

Using set membership (treating letters as reusable) instead of counts, or comparing counts for equality (==) as in an anagram when you only need supply ≥ demand.

How to stand out

Note the fail-fast length check, choose int[26] for the lowercase constraint, and decrement-on-the-fly returning false at the first negative — one pass after building counts.

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	Brute Force — Search and Strike Out (Don't Ship)	`O(n·m)`	`O(m)`	Mention briefly to show progression, then immediately move to counting — the O(n·m) cost is the giveaway.	Read
2	Frequency Count — int[26] / Hash Map (Optimal)Optimal	`O(n + m)`	`O(1)`	The answer they want. Phrase it as 'count the magazine's supply, then check it covers the note's demand'.	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

Brute Force — Search and Strike Out (Don't Ship)

TimeO(n·m)SpaceO(m)

Mention briefly to show progression, then immediately move to counting — the O(n·m) cost is the giveaway.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

Literal approach: for each letter of the note, find an unused copy in the magazine and 'cross it out'. What does 'find and remove' cost each time?

2Hint 2Explore hint

Searching the magazine for each note character and deleting it is a linear scan per character.

3Hint 3Explore hint

n note characters × O(m) search/delete each = O(n·m). Correct, but the repeated scanning is wasteful.

A · Core idea

The most literal model is physical: hold the magazine, and for each letter of the ransom note find that letter somewhere in the magazine and cut it out so it can't be reused.

B · Visual dry run

Interactive dry run

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

ransomNote = "aa", magazine = "aab"

note 'a' (1st)

find 'a' in "aab", strike it

Statemagazine → "ab"

Final resulttrue

C · Code with teaching comments

solution.javaJava

Brute Force — Search and Strike Out (Don't Ship) — reference

3 teaching notes

1
public boolean canConstruct(String ransomNote, String magazine) {
2
    StringBuilder pool = new StringBuilder(magazine);
3
    for (int i = 0; i < ransomNote.length(); i++) {
4
        // Linear search for an unused copy of this letter — the O(m) step done n times.
5
        int idx = pool.indexOf(String.valueOf(ransomNote.charAt(i)));
6
        // No copy left → the note can't be constructed.
7
        if (idx < 0) return false;
8
        // Consume the letter so it can't be reused — also O(m) due to shifting.
9
        pool.deleteCharAt(idx);
10
    }
11
    return true;
12
}

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

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

Repeatedly scanning to ask 'is there one left?' is the smell that a frequency count should replace the search. Whenever brute force re-scans for availability, precompute counts.

E · Edge cases and pitfalls4ransomNote = "a", magazine = "" — First lookup fails immediately → returns false.Explore edge cases

Edge cases handled

ransomNote = "a", magazine = ""First lookup fails immediately → returns false.

Pitfalls

Re-scanning the magazine for every note character — O(n·m) blows up at 10⁵.
Forgetting to remove the matched letter, which would allow illegal reuse.
Using indexOf/remove inside the loop and not realising each is itself O(m).

03.2

Approach 2 of 2 · Optimal

Frequency Count — int[26] / Hash Map (Optimal)

TimeO(n + m)SpaceO(1)

The answer they want. Phrase it as 'count the magazine's supply, then check it covers the note's demand'.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

You only ever ask 'are there enough of letter X left?'. What structure answers that in O(1) without rescanning?

2Hint 2Explore hint

Count every letter in the magazine into an int[26] (index = ch - 'a'). Then walk the note, decrementing the matching count.

3Hint 3Explore hint

If any count drops below 0, the magazine ran out of that letter → return false. Survive the whole note → return true.

A · Core idea

The problem is pure multiset containment: can the magazine's multiset of letters cover the ransom note's multiset? That reduces to one rule — for every letter, supply ≥ demand.

B · Visual dry run

Interactive dry run

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

ransomNote = "aa", magazine = "aab"

Hash-map state

magazine counted

ValueIndex / state

a→ 2

b→ 1

Match found

supply built from "aab"

Final resulttrue

C · Code with teaching comments

solution.javaJava

Frequency Count — int[26] / Hash Map (Optimal) — optimal

4 teaching notes

1
public boolean canConstruct(String ransomNote, String magazine) {
2
    // Fail fast — the magazine can't supply more letters than it has in total.
3
    if (ransomNote.length() > magazine.length()) return false;
4
    int[] counts = new int[26];
5
    for (int i = 0; i < magazine.length(); i++) {
6
        // Build the supply: char minus 'a' maps a..z to indices 0..25.
7
        counts[magazine.charAt(i) - 'a']++;
8
    }
9
    for (int i = 0; i < ransomNote.length(); i++) {
10
        // Consume a copy; a negative count means the magazine ran out of this letter.
11
        if (--counts[ransomNote.charAt(i) - 'a'] < 0) {
12
            return false;
13
        }
14
    }
15
    // Survived the whole note without exhausting any letter → constructible.
16
    return true;
17
}

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

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

E · Edge cases and pitfalls6ransomNote = "aa", magazine = "ab" — a: 1 → 0 on first 'a', then 0 → -1 on second 'a' → returns false.Explore edge cases

Edge cases handled

ransomNote = "aa", magazine = "ab"a: 1 → 0 on first 'a', then 0 → -1 on second 'a' → returns false.
ransomNote = "a", magazine = "a"a: 1 → 0, no negative → returns true.
ransomNote = "abc", magazine = "ab"Length check: 3 > 2 → returns false immediately.

Pitfalls

Comparing counts with == (anagram logic) instead of ≥ — leftover magazine letters are allowed.
Counting the ransom note instead of the magazine and getting the direction of the check backwards.
Forgetting the negative check after decrementing — the whole correctness hinges on it.

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.

Set membership instead of counts

A set ignores multiplicity, so it wrongly accepts note = "aa", magazine = "ab" (it sees 'a' exists). You must consume each letter once via counts.

Explore the code comparison

Don't write this

mag = set(magazine)
return all(ch in mag for ch in ransomNote)

Write this instead

counts = [0] * 26
for ch in magazine: counts[ord(ch) - 97] += 1
for ch in ransomNote:
    counts[ord(ch) - 97] -= 1
    if counts[ord(ch) - 97] < 0: return False
return True

Equality check (anagram confusion)

Ransom Note needs the magazine to COVER the note (supply ≥ demand), not match exactly. Comparing for equality rejects valid inputs with spare letters.

Explore the code comparison

Don't write this

from collections import Counter
return Counter(ransomNote) == Counter(magazine)

Write this instead

from collections import Counter
need, have = Counter(ransomNote), Counter(magazine)
return all(have[ch] >= cnt for ch, cnt in need.items())

Missing the negative check

Decrementing without checking for a negative count never detects exhaustion, so the function always returns true.

Explore the code comparison

Don't write this

counts[ransomNote.charAt(i) - 'a']--;
// no check, falls through to return true

Write this instead

if (--counts[ransomNote.charAt(i) - 'a'] < 0) {
    return false;
}

Revise

Carry the pattern into the interview

Quick interview revision

Pattern to remember

Frequency count + sufficiency check (counts must cover)

Code pattern to memorize

need = Counter(ransomNote)
have = Counter(magazine)
return all(have[ch] >= cnt for ch, cnt in need.items())

Rules to remember

1Each magazine letter can be used at most once → this is a multiset containment check, not a set check.
2Count the magazine (the supply), then make sure it covers every letter the note needs.
3Fail fast: if len(ransomNote) > len(magazine) it's immediately false — the note can't fit.
4Lowercase English only → an `int[26]` array beats a hash map on constant factors.
5Decrement-and-check-negative is equivalent to compare-counts; either works, but don't forget the negative check.
6Order and position are irrelevant — only multiplicities matter.

Use this pattern when

Check whether one multiset of characters can be built from another
'Can string A be formed using the letters of string B?' style prompts
Anagram / letter-availability problems with a fixed small alphabet
You need counts to cover (≥), not exactly match

Choose another pattern when

Letters can be reused unlimited times → it's a set-membership check, not counts
You must preserve order or contiguity → substring / subsequence problem
Exact equality of counts required → that's Valid Anagram, use ==
Alphabet is huge/unicode and memory is tight → hash map over fixed array

Interview takeaway

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

Valid Anagram
Same counting, but require exact equality (==) of all letter counts.
Group Anagrams
Use a frequency-derived signature as a grouping key.
Find All Anagrams in a String
Coming soon
Slide a fixed-size window and compare letter counts at each position.
Minimum Window Substring
Cover a demand multiset within a sliding window — coverage check at scale.

Same pattern

←

Repeated String

Continue · Next problem

Contains Duplicate II