A print shop rendered personalized notes by pulling letters from a magazine template. The first version nested a scan: for each character in the note, walk the magazine looking for an unused match, then scratch it. Staging notes of a dozen words returned instantly. A batch of campaign copy tens of thousands of characters long was still hunting unused letters when the renderer timed out.

Ransom Note asks whether magazine letter counts cover the note. charAt(i) is already free. Nested scratch uses that and still pays O(n · m). A count of the magazine answers “do we still have a copy?” without restarting the hunt.

This is an interview writeup, not a hashing lecture. The hash table post owns buckets and collisions. Here we only care about counting magazine letters so cover is a decrement, not a restart.

The problem

Given strings ransomNote and magazine, return true if you can build the note using letters from the magazine — each magazine letter used at most once — and false otherwise. Extra magazine letters are allowed. Assume lowercase English letters unless a follow-up widens the alphabet.

ransomNote = "code",  magazine = "decode"  →  true    extra d and e are fine
ransomNote = "skill", magazine = "silk"    →  false   two 'l's needed, one available
ransomNote = "maps",  magazine = "spam"    →  true    exact cover also works

Note: Sorting both copies and comparing equality is Valid Anagram’s honest brute, not this prompt. "code" and "decode" would fail that equality and still be a legal ransom. Do not sort.

Nested scratch is the honest brute force

For each note character, scan the magazine for an unused copy and mark it used. If any letter has no leftover match, return false. Correct. Quadratic.

boolean canConstructNested(String ransomNote, String magazine) {
    boolean[] used = new boolean[magazine.length()];
    for (int i = 0; i < ransomNote.length(); i++) {
        char need = ransomNote.charAt(i);
        boolean found = false;
        for (int j = 0; j < magazine.length(); j++) {
            if (!used[j] && magazine.charAt(j) == need) {
                used[j] = true;
                found = true;
                break;
            }
        }
        if (!found) {
            return false;
        }
    }
    return true;
}

At n = 20 this is a rounding error. At n in the tens of thousands you paid a nested scratch for a question a count answers in linear time: does the magazine still have a copy of this letter?

Count the magazine, then spend the note

If the note is longer than the magazine, return false immediately. Otherwise count every magazine letter into a 26-slot array. Walk the note and decrement. The first slot that goes below zero means the magazine cannot cover that letter. If the walk finishes, return true.

You never restart a magazine scan from index 0. You never require leftover counts to be zero. A HashMap is the same idea when the alphabet is not 26 letters.

ransomNote = "code"   magazine = "decode"

count magazine:  c:1 o:1 d:2 e:2
c → 0
o → 0
d → 1
e → 1
never below zero → true

The Java is that walk:

boolean canConstruct(String ransomNote, String magazine) {
    if (ransomNote.length() > magazine.length()) {
        return false;
    }
    int[] count = new int[26];
    for (int i = 0; i < magazine.length(); i++) {
        count[magazine.charAt(i) - 'a']++;
    }
    for (int i = 0; i < ransomNote.length(); i++) {
        int slot = ransomNote.charAt(i) - 'a';
        count[slot]--;
        if (count[slot] < 0) {
            return false;
        }
    }
    return true;
}

Time is O(n + m) — one pass over the magazine, one over the note. Space is O(1) for the fixed alphabet. A map would pay extra space if the follow-up opens Unicode; that layout is the hash-table post, not this board.

Note: A longer note than the magazine is an early false. That is not Valid Anagram. Anagram needs exact frequencies both ways. Ransom is cover: leftover magazine letters are allowed; leftover note letters are not.

What interviewers usually poke next

  • Unicode, not just a–z. The 26-slot array is a lie. Use a map, same count-then-spend, unbounded keys.
  • First Unique Character. Same count table, different question: that prompt asks for the first index whose count is 1; this one asks whether one bag covers another.
  • Valid Anagram. Exact frequencies both ways. "code" / "decode" is a true ransom and a false anagram. Say the difference out loud.
  • Count the note first. Tally both strings, then check magazine[c] >= note[c] for every letter. Same cover test; you lose the early false on the first missing letter unless you still fail when a note count exceeds the magazine mid-walk. Magazine-first decrement is the usual board answer.

You are done with this problem when you can say, out loud, why scratching each note letter in the magazine is correct, why magazine counts covering the note is the expected answer, and why anagram equality is the wrong test.