Ransom Note
Last Updated: April 6, 2026
Understanding the Problem
At its core, 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.
The key constraint is that 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. We need to verify this for every letter in the ransom note.
This boils down to: 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. This means we can use a fixed-size array of length 26 instead of a hash map, giving us true O(1) space.
Approach 1: Brute Force (Search and Remove)
Intuition
The most straightforward way to think about this: go through the ransom note letter by letter. For each letter, search the magazine for a matching letter. If you find one, cross it out (remove it so it can't be reused). If you can't find a match, the ransom note can't be constructed.
This mimics how you'd physically cut letters out of a magazine to compose a note.
Algorithm
- Convert the magazine string into a mutable structure (like a list of characters or a StringBuilder).
- For each character in the ransom note:
- Search the magazine for this character.
- If found, remove that character from the magazine (so it can't be reused).
- If not found, return false.
- If we process every ransom note character successfully, return true.
Example Walkthrough
Code
- Time Complexity: O(m * n). For each of the m characters in the ransom note, we search through up to n characters in the magazine. The find/indexOf operation is O(n), and removing an element from the middle is also O(n).
- Space Complexity: O(n). We create a mutable copy of the magazine string, which takes O(n) space.
For every character in the ransom note, we're scanning the entire magazine to find a match. When both strings are close to 10^5 characters, that's up to 10^10 operations. What if we sorted both strings so identical characters were grouped together?
Approach 2: Sorting + Two Pointers
Intuition
If we sort both strings, all identical characters are grouped together. Then we can walk through both sorted strings simultaneously with two pointers, checking if the magazine has enough of each character.
Think of it like lining up two sorted lists side by side. As long as every character the ransom note needs appears at least as many times in the magazine, we're good.
Algorithm
- Sort both
ransomNoteandmagazineby character. - Initialize two pointers:
ifor the ransom note,jfor the magazine. - While both pointers are within bounds:
- If
ransomNote[i] == magazine[j], we've matched a character. Move both pointers forward. - If
ransomNote[i] > magazine[j], the magazine character is too small. Movejforward to find a match. - If
ransomNote[i] < magazine[j], the ransom note needs a character the magazine doesn't have. Return false. - If we've matched all characters in the ransom note (
ireached the end), return true. Otherwise, return false.
Example Walkthrough
Code
- Time Complexity: O(m log m + n log n). Sorting the ransom note takes O(m log m) and sorting the magazine takes O(n log n). The two-pointer scan is O(m + n), which is dominated by the sorting step.
- Space Complexity: O(m + n). Depending on the language, sorting may require O(m) or O(n) extra space. The conversion from string to array also takes space.
Sorting both strings costs O(m log m + n log n), and we haven't even started comparing yet. But we don't actually need the characters in order. All we need is a count of how many times each character appears. Can we get those counts in a single pass?
Approach 3: Counting Array (Optimal)
Intuition
Since we only care about whether the magazine has enough of each letter, we can skip sorting entirely. Just count how many times each character appears in the magazine, then check if the ransom note's character demands are met.
Here's the neat part: since the input only has lowercase English letters, there are exactly 26 possible characters. We can use a simple integer array of size 26 instead of a hash map. This gives us constant space and avoids any hashing overhead.
The approach works in two passes: first, count the supply (magazine characters). Then, check the demand (ransom note characters) against the supply.
The counting array acts as a ledger. Each magazine character adds to the balance, and each ransom note character withdraws from it. If a withdrawal causes the balance to go negative, the magazine is short on that letter. The fixed array size of 26 means we're using constant space regardless of input size.
This is a common pattern with character-frequency problems. Whenever you need to compare "does string A have at least as many of each character as string B," a frequency count is the natural tool.
Algorithm
- Create an integer array
countof size 26, initialized to zeros. - For each character in the magazine, increment
count[c - 'a']. - For each character in the ransom note, decrement
count[c - 'a']. - If any count drops below zero, the magazine doesn't have enough of that character. Return false.
- If we process all ransom note characters without going negative, return true.
Example Walkthrough
Code
- Time Complexity: O(m + n). We make one pass through the magazine (n characters) to build the count, and one pass through the ransom note (m characters) to check it. Each operation within the loop is O(1).
- Space Complexity: O(1). The count array is always size 26, regardless of input size. This is constant space.