Ransom Note

EasyProblemExternal linkUpdated Oct 25, 2026

Description

You get two strings, ransomNote and magazine.

Return true if ransomNote can be written using letters cut from magazine, and false otherwise. Each letter in magazine can be used only once.

Examples

Example 1

Input: ransomNote = "a", magazine = "b"

Output: false

Explanation: The note needs an a, and the magazine has none: false.

Example 2

Input: ransomNote = "aa", magazine = "ab"

Output: false

Explanation: The note needs two a's, and the magazine has only one: false.

Example 3

Input: ransomNote = "aa", magazine = "aab"

Output: true

Explanation: Two a's for the note, and the b is left over, which is fine: true.

Constraints

1 ≤ ransomNote.length, magazine.length ≤ 10^5
ransomNote and magazine consist of lowercase English letters.

Editorial

Brute Force

Intuition

Do it the way you would with real paper: for each letter of the note, find that letter in what's left of the magazine and cut it out. If a letter can't be found, the note can't be written.

Step-by-Step Explanation

Let's cut "abca" out of "aabbc":

The note needs a. The first a left is at position 0, after scanning 1 letter. Cut it out.
The note needs b. The first b left is at position 1, after scanning 2 letters. Cut it out.
The note needs c. The first c left is at position 2, after scanning 3 letters. Cut it out.
The note needs a. The first a left is at position 0, after scanning 1 letter. Cut it out.

The note can be written.

Cut Each Letter Out — The row is what's left of the magazine. Each step finds the note's next letter (green) and cuts it out.

Algorithm

Copy the magazine's letters into a list.
For each letter of the note: find it in the list; if it isn't there, return false; otherwise remove it.
Return true.

Code

class Solution {
public:
    bool canConstruct(string ransomNote, string magazine) {
        for (char c : ransomNote) {
            size_t p = magazine.find(c);        // look for c among the letters still left
            if (p == string::npos) return false;
            magazine.erase(p, 1);               // cut it out, so it can't be used again
        }
        return true;
    }
};

class Solution:
    def canConstruct(self, ransomNote: str, magazine: str) -> bool:
        letters = list(magazine)
        for c in ransomNote:
            if c not in letters:                # look for c among the letters still left
                return False
            letters.remove(c)                   # cut it out, so it can't be used again
        return True

class Solution {
    public boolean canConstruct(String ransomNote, String magazine) {
        StringBuilder letters = new StringBuilder(magazine);
        for (char c : ransomNote.toCharArray()) {
            int p = letters.indexOf(String.valueOf(c));   // look for c among the letters still left
            if (p < 0) return false;
            letters.deleteCharAt(p);                       // cut it out, so it can't be used again
        }
        return true;
    }
}

var canConstruct = function(ransomNote, magazine) {
    const letters = magazine.split('');
    for (const c of ransomNote) {
        const p = letters.indexOf(c);           // look for c among the letters still left
        if (p < 0) return false;
        letters.splice(p, 1);                   // cut it out, so it can't be used again
    }
    return true;
};

Complexity Analysis

Time Complexity: O(n · m)

For each of the note's n letters, finding and removing one from the magazine's m letters can scan and shift all of them.

Space Complexity: O(m) for the copy.

Why This Approach Is Not Efficient

With 10^5 letters in each string, that's up to 10^10 steps (over the time limit in Python and javascript).

And the question doesn't care where the letters are, only how many of each there are. Count the magazine once, and each note letter becomes a lookup and a subtraction.

Optimal Approach - Counting

Intuition

Count how many of each letter the magazine has: 26 counters, one per letter. Then spend them: for each letter of the note, if its counter is 0 the magazine has run out of it, so the answer is false; otherwise take one. If the whole note is spent, the answer is true.

Letters the magazine has left over don't matter, so this isn't an anagram check: the magazine only has to cover the note.

Step-by-Step Explanation

Let's count "aabbc" and spend it on "abca":

Count the magazine once, which gives 2 a, 2 b, 1 c.
The note needs a, and one is left to spend. Its count drops to 1.
The note needs b, and one is left to spend. Its count drops to 1.
The note needs c, and one is left to spend. Its count drops to 0.
The note needs a, and one is left to spend. Its count drops to 0.

Every letter was there.

Count the Magazine, Spend the Note — The table is the magazine's count for each letter. Each step spends one for the note's next letter.

Algorithm

Count every letter of magazine into an array of 26.
For each letter of ransomNote: if its count is 0, return false; otherwise subtract 1.
Return true.

Code

class Solution {
public:
    bool canConstruct(string ransomNote, string magazine) {
        int count[26] = {0};                    // what the magazine offers, letter by letter
        for (char c : magazine) count[c - 'a']++;
        for (char c : ransomNote) {
            if (count[c - 'a'] == 0) return false;   // this letter has run out
            count[c - 'a']--;
        }
        return true;
    }
};

class Solution:
    def canConstruct(self, ransomNote: str, magazine: str) -> bool:
        count = [0] * 26                        # what the magazine offers, letter by letter
        for c in magazine:
            count[ord(c) - ord('a')] += 1
        for c in ransomNote:
            k = ord(c) - ord('a')
            if count[k] == 0:
                return False                    # this letter has run out
            count[k] -= 1
        return True

class Solution {
    public boolean canConstruct(String ransomNote, String magazine) {
        int[] count = new int[26];              // what the magazine offers, letter by letter
        for (char c : magazine.toCharArray()) count[c - 'a']++;
        for (char c : ransomNote.toCharArray()) {
            if (count[c - 'a'] == 0) return false;   // this letter has run out
            count[c - 'a']--;
        }
        return true;
    }
}

var canConstruct = function(ransomNote, magazine) {
    const count = new Array(26).fill(0);        // what the magazine offers, letter by letter
    for (const c of magazine) count[c.charCodeAt(0) - 97]++;
    for (const c of ransomNote) {
        const k = c.charCodeAt(0) - 97;
        if (count[k] === 0) return false;       // this letter has run out
        count[k]--;
    }
    return true;
};

Complexity Analysis

Time Complexity: O(n + m)

One pass over the magazine, one over the note.

Space Complexity: O(1)

26 counters, whatever the lengths.

Common Mistakes

Each of these looks right on a quick read, and the tests still reject it. The outputs below come from running the code.

Checking which letters, not how many. return set(ransomNote) <= set(magazine)

On ransomNote = "aa", magazine = "ab", it returns true; the answer is false. Every letter of the note appearing somewhere in the magazine isn't enough: the note may need a letter more times than the magazine has it. Count the copies.

Checking for a negative count before spending. if count[k] < 0: return False

On ransomNote = "bbbbb", magazine = "bbbb", it returns true; the answer is false. Spending first and then checking for a count below 0 is fine, but checking < 0 before the spend lets every letter be used one extra time. Check that a copy is left (count above 0) before you take it.

Comparing the lengths. return len(ransomNote) <= len(magazine)

On ransomNote = "ab", magazine = "cd", it returns true; the answer is false. A magazine at least as long as the note can still be missing the letters the note needs.

Where This Pattern Is Taught

This problem practises counting with a hash table: one count table covering another. It's taught in Frequency Counting with Hash Maps.