EasyHash TableStringCountingUpdated Sep 2026

383. Ransom Note

Asked at Anduril

Difficulty

Easy

Time

O(n + m)

Space

O(1)

Pattern

Hash Table

Companies

1

Problem

You are given two strings: ransomNote and magazine. Return true if you can build ransomNote using letters taken from magazine, and false if you cannot.

Each letter in magazine may be used at most once. So if the note needs two a characters, the magazine must contain at least two a characters.

Only the counts of letters matter. The order of letters in the magazine does not matter, and you may pick letters from any position.

Cut letters from the magazine

ransomNoteaa01The note asks for two 'a' charactersmagazineab01The magazine can give only one 'a' — not enough
Each magazine letter can be used once. Here the note needs two 'a' but the magazine only has one, so the answer is false.

Constraints

  • ●1 <= ransomNote.length, magazine.length <= 10^5
  • ●ransomNote and magazine consist of lowercase English letters only

Examples

Example 1
InputransomNote = "a", magazine = "b"
Outputfalse
WhyThe note needs one 'a', but the magazine only has a 'b'. There is no 'a' to cut out.
Example 2
InputransomNote = "aa", magazine = "ab"
Outputfalse
WhyThe note needs two 'a' characters, but the magazine has only one. The single 'a' can be used once, so the second 'a' cannot be filled.
Example 3
InputransomNote = "aa", magazine = "aab"
Outputtrue
WhyThe magazine has two 'a' characters and one 'b'. The note only needs the two 'a' characters, so we can build it. The extra 'b' is simply not used.

Asked At

1 companies
CompanyDifficulty
AndurilEasyView all Anduril questions →

How to Think About It

1

Brute force: for each letter in the note, search the magazine and remove the first match. That is O(n * m).

2

Key insight: only letter counts matter, not positions. Count each letter in the magazine, then spend those counts on the note.

3

Use a 26-length array since the inputs are lowercase letters. Increment for magazine letters; decrement for note letters and fail as soon as a count goes negative.

4

Walkthrough: note "aa", magazine "aab": counts a=2, b=1. Spend a twice -> a=0. Never negative -> true. Note "aa", magazine "ab" -> second a drives the count to -1 -> false.

5

Quick exit: if the note is longer than the magazine, the answer is false.

Optimal Approach

Step 1: If len(ransomNote) > len(magazine), return false.
Step 2: count = [0] * 26; for each char in magazine, increment its count.
Step 3: For each char in ransomNote: decrement its count; if it becomes negative, return false.
Step 4: Return true.

Time: O(n + m). Space: O(1) (26 counters).

Count letters, then spend them

countab21Step 1 — count the magazine "aab": a=2, b=1countab01Step 2 — spend the note "aa": subtract a twice,leaving a=0count[ch] -= 1if count[ch] < 0: return falsenever negative → return true
Count every magazine letter, then subtract one count per note letter. If any count goes below zero, we ran out.
ComplexityTime O(n + m)Space O(1)We scan the magazine once and the note once; the 26 counters are a fixed-size array, so the extra space does not grow with the input.

What Trips People Up in Real Interviews

1

Checking membership only (ch in magazine). That ignores multiplicity — the note "aa" cannot be built from the magazine "a".

2

Mutating strings with replace to remove used letters. It works but is quadratic and allocates new strings every time.

3

Counting the note and the magazine separately and then comparing — fine, but the single table with early exit is simpler.

4

Not asking about the character set. If Unicode is possible, switch the array to a hash map.

Solution Code

O(n + m) time
def canConstruct(ransomNote, magazine):
    if len(ransomNote) > len(magazine):
        return False
    count = [0] * 26
    for ch in magazine:
        count[ord(ch) - ord('a')] += 1
    for ch in ransomNote:
        i = ord(ch) - ord('a')
        count[i] -= 1
        if count[i] < 0:
            return False
    return True

Pro at DSA?

Test your skills with a real FAANG-style mock interview.

Start a Mock Interview →

Frequently Asked Questions

What is the Ransom Note problem?

Ransom Note asks whether you can build the string `ransomNote` using letters cut out of `magazine`, where each magazine letter can be used only once. It is a quick counting question that checks you reach for a frequency table instead of searching the magazine repeatedly.

How do you solve Ransom Note?

The optimal approach runs in O(n + m) time and O(1) space. Scroll up to "Optimal Approach" for the step-by-step walkthrough, diagrams, and code in Python, C++ and Java.

What companies ask Ransom Note?

Ransom Note is asked at Anduril. It is a easy difficulty problem.

What are common mistakes on Ransom Note?
  • Checking membership only (`ch in magazine`). That ignores multiplicity — the note `"aa"` cannot be built from the magazine `"a"`.
  • Mutating strings with `replace` to remove used letters. It works but is quadratic and allocates new strings every time.
  • Counting the note and the magazine separately and then comparing — fine, but the single table with early exit is simpler.
  • Not asking about the character set. If Unicode is possible, switch the array to a hash map.