Ransom Note

The Ransom Note problem is a staple in coding interviews because it tests your ability to reason about resource availability, counting, and efficient lookup operations. At its core, the challenge is a frequency-matching exercise: can you build one string using the characters from another string, with no reuse beyond what the source provides?

This problem highlights one of the most important patterns in string manipulation: using fixed-size frequency arrays or hash maps to compare character availability.

Problem

You are given two strings, ransomNote and magazine. Your task is to determine whether you can construct the string ransomNote using characters from magazine.

Rules:

• Each character in magazine can be used at most once.
• All characters are lowercase English letters.
• Order does not matter—only character counts do.

Return:

• true if the ransom note can be formed from the magazine.
• false otherwise.

Example

Input:

ransomNote = "a"

magazine = "b"

Output:

false

Reason: The magazine does not contain the character “a”.

Input:

ransomNote = "aa"

magazine = "aab"

Output:

true

Reason: magazine has two ‘a’ characters and one ‘b’, so it can supply all required characters.

Solution

The most efficient way to solve this problem is to count the frequency of each character in both strings and verify that the magazine has at least as many of each character as the ransom note requires.

Since both strings contain only lowercase letters (a–z), we can use a fixed-size array of length 26 instead of a hash map, which is faster and uses constant space.

Key idea

For every character in ransomNote:

• Check if the magazine has enough copies of that character.
• If not, return false immediately.
• If all characters from ransomNote are accounted for, return true.

This turns the entire problem into a simple multiset comparison.

Why this works

• Lowercase letters allow a constant-size frequency array.
• Character counting runs in \( O(n + m) \) time, where n and m are the lengths of the two strings.
• We only need \( O(1) \) extra space because the array size never changes.

This makes the solution extremely efficient even for large input sizes.

Algorithm outline

1. Create an array count[26] initialized to zeros.
2. For every character c in magazine, increment count[c].
3. For every character c in ransomNote:
   • Decrement count[c].
   • If it becomes negative at any point, return false.
4. If the loop completes, return true.

Sample implementation (Python)

Alternative solution: hash map

You can use a dictionary instead of a 26-element array.

This is more flexible if characters are not restricted to lowercase.

Poor solution: repeated scanning

Searching for characters one by one in the magazine leads to \( O(n²) \) behavior and fails when characters repeat. Avoid this approach.

Interview insight

The Ransom Note problem is a favorite for testing:

• Your understanding of counting and frequency maps
• Your ability to optimize using a fixed-size data structure
• Your instinct to avoid unnecessary sorting or repeated scanning

It’s closely related to a whole family of problems such as anagrams, character inventories, and multiset comparisons. Mastering it prepares you for more complex variations involving substring windows, frequency constraints, and sliding window optimizations.