Ransom Note

EasyHashing · Character Counting🧩 Hashing & Counting LeetCode #383 ↗Updated Oct 30, 2026

Problem

You want to build the string ransomNote by cutting letters out of the string magazine. Every letter of magazine can be used at most once, and order does not matter. Return true if the note can be assembled, otherwise false.

InputransomNote = "a", magazine = "b"Outputfalse

InputransomNote = "aa", magazine = "ab"Outputfalse

InputransomNote = "aa", magazine = "aab"Outputtrue

1 ≤ ransomNote.length, magazine.length ≤ 10⁵ · only lowercase English letters

Try it yourself

Java

class Solution {
    public boolean canConstruct(String ransomNote, String magazine) {
        
    }
}

Your code is saved in this browser.Submit on LeetCode ↗

Key insight

Order is irrelevant, so each string is fully described by its letter counts. The note is buildable iff, for every letter, the magazine has at least as many copies as the note needs.

PatternHashing & Counting

Instinct Need "have I seen this before?", "how many times?" or "group things that look alike"? Trade memory for O(1) lookups with a HashMap, HashSet or int[26].

Memory hack Don't search, remember - every element checks in at the front desk, and the desk answers instantly.

Open the Hashing & Counting guide →

Approaches

Brute ForceFind & Remove Each Letter

Time O(m · n)Space O(n)

Copy the magazine into a mutable buffer. For each letter of the note, search the buffer for a matching letter and delete it so it cannot be reused; if none is found, the note is impossible. (m = note length, n = magazine length.)

Java

public boolean canConstruct(String ransomNote, String magazine) {
    StringBuilder pool = new StringBuilder(magazine);
    for (char c : ransomNote.toCharArray()) {
        int at = pool.indexOf(String.valueOf(c));
        if (at < 0) return false;  // letter not available any more
        pool.deleteCharAt(at);     // use it up
    }
    return true;
}

Mirrors the physical process, but every search and deletion is O(n).

BetterSort Both, Two Pointers

Time O(m log m + n log n)Space O(m + n)

Sort the characters of both strings. Walk the magazine with pointer j; each note letter must find an equal magazine letter at or after j. Smaller magazine letters are skipped (unused); a larger one means the needed letter is missing.

Java

public boolean canConstruct(String ransomNote, String magazine) {
    char[] note = ransomNote.toCharArray();
    char[] mag = magazine.toCharArray();
    Arrays.sort(note);
    Arrays.sort(mag);
    int j = 0;
    for (char c : note) {
        while (j < mag.length && mag[j] < c) j++; // skip letters we don't need
        if (j == mag.length || mag[j] != c) return false;
        j++; // consume the matching letter
    }
    return true;
}

No repeated searching, but sorting dominates and needs char-array copies.

Optimal26-Slot Count Array

Time O(m + n)Space O(1)

Count every magazine letter into an int[26]. Then spend counts for each note letter; the moment a count would go negative, the magazine has run out of that letter.

Java

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

Dry runransomNote = "a", magazine = "b"

i note index changed

count
a

a

magazine: a=2 b=1
i=0
a
i
a

a: 2→1
i=1
a

a
i
a: 1→0 → true ✔

Linear, constant extra space, early exit on the first shortage.

Pro tip

The length check up front rejects many inputs in O(1) before any counting.

At a glance

Level	Approach	Time	Space
Brute Force	Find & Remove Each Letter	`O(m · n)`	`O(n)`
Better	Sort Both, Two Pointers	`O(m log m + n log n)`	`O(m + n)`
Optimal	26-Slot Count Array	`O(m + n)`	`O(1)`

Common pitfalls

Only checking that each letter exists — "aa" vs "ab" needs two a's.
Swapping the roles: counting the note and spending from the magazine is fine, mixing them is not.
Using String.replaceFirst in a loop — regex overhead and still O(m·n).

Interview tips

Clarify the alphabet; for Unicode, use a HashMap<Character,Integer>.
Mention it is a multiset-containment question: note ⊆ magazine.
Call out the early exit and the length shortcut as easy optimisations.

Pattern

Frequency table → when order doesn't matter and you compare how many of each item two collections have.

My notes saved in this browser