AlgoMaster Logo

Ransom Note

easyFrequency6 min readUpdated June 23, 2026

Understanding the Problem

This is a character availability problem. We have a supply of letters (the magazine) and a demand for letters (the ransom note). For every character the ransom note needs, the magazine must have at least that many copies available.

Each magazine letter can only be used once. So if the ransom note needs three 'a's, the magazine must contain at least three 'a's, and the same must hold for every other letter the note uses.

The question reduces to one comparison: does the character frequency of the ransom note fit within the character frequency of the magazine?

Key Constraints:

  • 1 <= ransomNote.length, magazine.length <= 10^5 → With up to 100,000 characters, an O(m * n) brute force might be tight but an O(m + n) solution is comfortable.
  • ransomNote and magazine consist of lowercase English letters → Only 26 possible characters. We can use a fixed-size array of length 26 instead of a hash map, giving O(1) space.

Approach 1: Brute Force (Search and Remove)

Intuition

Go through the ransom note letter by letter. For each letter, search the magazine for a matching letter. If a match exists, remove it so it can't be reused. If no match exists, the ransom note can't be constructed.

This mirrors physically cutting letters out of a magazine to compose a note: every letter you use is gone from the supply.

Algorithm

  1. Convert the magazine string into a mutable structure (like a list of characters or a StringBuilder).
  2. For each character in the ransom note:
    1. Search the magazine for this character.
    2. If found, remove that character from the magazine (so it can't be reused).
    3. If not found, return false.
  3. If we process every ransom note character successfully, return true.

Example Walkthrough

ransomNote
1Process each character of ransomNote against magazine
0
a
1
a
2
b
magazine (mutable list)
1Convert magazine to mutable list: [a, a, b, c, d]
[a, a, b, c, d]
1/8

Code

For every character in the ransom note, this scans the entire magazine to find a match. When both strings are close to 10^5 characters, that is up to 10^10 operations, well beyond what runs in time. Sorting both strings groups identical characters together, which removes the repeated scanning.

Approach 2: Sorting + Two Pointers

Intuition

If we sort both strings, all identical characters are grouped together. We can then walk through both sorted strings with two pointers, advancing the magazine pointer until it catches up to each character the ransom note needs.

Because both strings are sorted, a character in the ransom note that is smaller than the current magazine character can never appear later in the magazine, so the magazine is missing it and the answer is false.

Algorithm

  1. Sort both ransomNote and magazine by character.
  2. Initialize two pointers: i for the ransom note, j for the magazine.
  3. While both pointers are within bounds:
    1. If ransomNote[i] == magazine[j], we've matched a character. Move both pointers forward.
    2. If ransomNote[i] > magazine[j], the magazine character is too small. Move j forward to find a match.
    3. If ransomNote[i] < magazine[j], the ransom note needs a character the magazine doesn't have. Return false.
  4. If we've matched all characters in the ransom note (i reached the end), return true. Otherwise, return false.

Example Walkthrough

sorted ransomNote
1After sorting: ransomNote = "aab", magazine = "aabcd"
0
a
1
a
2
b
sorted magazine
1Sorted magazine: "aabcd"
0
a
1
a
2
b
3
c
4
d
1/5

Code

Sorting both strings costs O(m log m + n log n) before any comparison happens. The order of characters is irrelevant to the answer; only the count of each character matters. Those counts can be gathered in a single linear pass.

Approach 3: Counting Array (Optimal)

Intuition

Since the only thing that matters is whether the magazine has enough of each letter, we can skip sorting. Count how many times each character appears in the magazine, then check the ransom note's demands against those counts.

Because the input is restricted to lowercase English letters, there are exactly 26 possible characters. An integer array of size 26 replaces a hash map here, which gives constant space and avoids hashing overhead.

The work happens in two passes: first count the supply (magazine characters), then check the demand (ransom note characters) against it.

Algorithm

  1. Create an integer array count of size 26, initialized to zeros.
  2. For each character in the magazine, increment count[c - 'a'].
  3. For each character in the ransom note, decrement count[c - 'a'].
  4. If any count drops below zero, the magazine doesn't have enough of that character. Return false.
  5. If we process all ransom note characters without going negative, return true.

Example Walkthrough

magazine
1Start: ransomNote = "aa", magazine = "aab", count = [0]*26
0
a
1
a
2
b
ransomNote
1ransomNote = "aa"
0
a
1
a
count (showing non-zero only)
1Initialize count array of size 26, all zeros
1/6

Code