#383 Ransom Note

frequently reported atApple Microsoft Amazon

the problem

In plain words

Can you build the string ransomNote using letters cut out of the string magazine? Each letter of magazine can be used only once. Return true or false.

in ransomNote = "a", magazine = "b"

out false

in ransomNote = "aa", magazine = "ab"

out false

The magazine has only one 'a'.

in ransomNote = "aa", magazine = "aab"

out true

1 ≤ ransomNote.length, magazine.length ≤ 10⁵
Lowercase English letters

your turn

Try it before you peek

Read the examples, say the brute force out loud, then write code: here or on LeetCode ↗. Stuck for 20 minutes? Open one hint at a time.

Solve it in the browser

LeetCode-style: complete the class. Compiled by the real javac (Java 17) and judged right here — nothing is sent anywhere.

Solutions are hidden so you can try first. Even 20 minutes of real effort makes the answer stick far better than reading it.

Marking the problem solved, or opening every hint, also shows it.

the aha

Key insight

patternFrequency counting

Order doesn't matter, only stock. Count each letter the magazine has, then spend those counts on the note; running out of any letter means false.

solutions

From brute force to optimal

For each note letter, search the remaining magazine text and delete one copy.

left = a StringBuilder copy of magazine.
For each note letter: find it with indexOf; missing → false.
deleteCharAt to cross it out.

timeO(n · m)

Each of the n note letters searches and shifts up to m magazine letters.

spaceO(m)

The mutable copy of the magazine.

javajava.util.*

1class Solution {2    public boolean canConstruct(String ransomNote, String magazine) {3        StringBuilder left = new StringBuilder(magazine);  // letters we can still cut out4        for (char c : ransomNote.toCharArray()) {5            int at = left.indexOf(String.valueOf(c));      // O(m) search…6            if (at < 0) return false;7            left.deleteCharAt(at);                         // …and an O(m) shift to cross it out8        }9        return true;10    }11}

Count the magazine with merge, then decrement for each note letter.

stock.merge(c, 1, Integer::sum) for the magazine.
For each note letter: left = getOrDefault(c, 0); 0 → false; else store left − 1.

timeO(n + m)

One pass over each string, O(1)-average map work per letter.

spaceO(1)

At most 26 keys — but each update boxes and hashes.

javajava.util.*

1class Solution {2    public boolean canConstruct(String ransomNote, String magazine) {3        Map<Character, Integer> stock = new HashMap<>();4        for (char c : magazine.toCharArray()) stock.merge(c, 1, Integer::sum);5        for (char c : ransomNote.toCharArray()) {6            int left = stock.getOrDefault(c, 0);7            if (left == 0) return false;                   // the magazine ran out of c8            stock.put(c, left - 1);9        }10        return true;11    }12}

Same counting with an array: c - 'a' is the index.

Note longer than magazine → false.
stock[c − 'a']++ for the magazine.
--stock[c − 'a'] < 0 for a note letter → false.
Return true.

timeO(n + m)

One pass over each string with plain array access.

spaceO(1)

26 counters.

javajava.util.*

1class Solution {2    public boolean canConstruct(String ransomNote, String magazine) {3        if (ransomNote.length() > magazine.length()) return false; // can't need more letters than exist4        int[] stock = new int[26];5        for (int i = 0; i < magazine.length(); i++) stock[magazine.charAt(i) - 'a']++;6        for (int i = 0; i < ransomNote.length(); i++) {7            if (--stock[ransomNote.charAt(i) - 'a'] < 0) return false; // used one more than we had8        }9        return true;10    }11}

in the room

How to say it in the interview

talk track

Ask: lowercase letters only? Then an int[26] is enough.
Mention the early exit: a note longer than the magazine can never be built.

traps

Checking only whether each letter appears in the magazine (contains), not how many times: "aa" vs "ab" wrongly passes.
Counting both strings upwards and then comparing in the wrong direction — the magazine needs ≥ the note for every letter.

what they ask next

Follow-ups

Any Unicode characters?

Count code points in a HashMap<Integer, Integer>, exactly like Valid Anagram's follow-up.

before you submit

Edge cases to test

Note longer than the magazine → false at once.
A letter needed twice but stocked once ("aa" vs "ab") → false.
Note equal to the magazine → true.

practise next