How do you solve Ransom Note?

Use a Counter to store character frequencies from magazine. Iterate through ransomNote, decrementing the count for each character. If any count becomes negative, return false immediately. If all characters are accounted for, return true.

Ransom Note

Q: What is the time complexity of Ransom Note?

O(n + m). Counting frequencies in magazine takes O(m), iterating through ransomNote takes O(n), where n and m are the lengths of ransomNote and magazine respectively.

Q: What pattern does Ransom Note use?

The Pattern: Hash Maps (Frequency Counting) The Heuristic: When verifying if one collection can be formed from another with limited resources, use a hash map to count available elements and decrement counts as you consume them, enabling O(n) verification.

Easy Hash Maps

Problem

Given two strings ransomNote and magazine, return true if ransomNote can be constructed from the letters in magazine and false otherwise.

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

Example

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

Output: false

The ransom note requires the letter 'a', but the magazine only contains 'b', so it is impossible to construct the ransom note.

Approach

Straightforward Solution

A brute-force approach would check for each character in ransomNote whether it exists in magazine and remove it once found, resulting in O(n*m) time complexity, which is inefficient for large inputs.

Core Observation

The problem reduces to verifying if the frequency of each character in ransomNote does not exceed its frequency in magazine.

Path to Optimal

Preview

By counting the frequency of each character in magazine using a hash map (or Counter), the problem transforms into a simple frequency comparison…

Full step-by-step walkthrough on Pro →

Optimal Approach

Preview

Use a Counter to store character frequencies from magazine. Iterate through ransomNote, decrementing the count for each character…

Full step-by-step walkthrough on Pro →

Want the full reasoning chain?

Unlock the complete walkthrough, line-by-line analysis, and recall drill.

Unlock Pro

Time

O(n + m)

Counting frequencies in magazine takes O(m), iterating through ransomNote takes O(n), where n and m are the lengths of ransomNote and magazine respectively.

Space

O(1)

The hash map stores counts for lowercase English letters only, which is a fixed size of 26, resulting in O(1) auxiliary space.

Pattern Spotlight

Hash Maps (Frequency Counting)

When verifying if one collection can be formed from another with limited resources, use a hash map to count available elements and decrement counts as you consume them, enabling O(n) verification.

Solution

Python

1from collections import Counter
2
3class Solution:
4    def canConstruct(self, ransomNote: str, magazine: str) -> bool:
5        available_chars = Counter(magazine)
6
7        for char in ransomNote:
8            if available_chars[char] == 0:
9                return False
10
11            available_chars[char] -= 1
12
13        return True

Step-by-Step Solution

Build Frequency Map of Magazine Characters

5	`available_chars = Counter(magazine)`

Objective

To count the number of occurrences of each character in magazine for quick availability checks.

Key Insight

Using a hash map (Counter) to store character frequencies allows constant-time lookups and updates, transforming the problem from repeated searches to simple arithmetic checks. This precomputation is essential for efficient verification.

Interview Quick-Check

Core Logic

The Counter data structure efficiently maps each character to its frequency, enabling O(1) average-time access for decrementing counts.

Complexity

Counting frequencies is O(m) time, where m is the length of magazine.

Verify Ransom Note Construction by Decrementing Counts

To iterate through ransomNote and check if each character is available in magazine by decrementing its count.

Return True if All Characters are Sufficient

To confirm that all characters in ransomNote are available in magazine and return true.

2 more steps with full analysis available on Pro.

Line Analysis

This solution has 3 Critical lines interviewers watch for.

Line 8 Critical

if available_chars[char] == 0:

Check if the current character is unavailable in magazine.

If the count is zero, it means magazine lacks sufficient instances of this character, so the ransom note cannot be constructed.

Line 5 Critical

available_chars = Counter(magazine)

Create a frequency map of characters in magazine using Counter.

This line efficiently counts all characters in magazine, enabling constant-time lookups and updates for character availability checks.

Line 11 Critical

available_chars[char] -= 1

Decrement the count of the current character in the frequency map.

This simulates using one instance of the character from magazine, ensuring no character is overused beyond availability.

Full line-by-line criticality + rationale for all 6 lines available on Pro.

Test Your Understanding

Why is it necessary to decrement the count of characters in the hash map when iterating through ransomNote?

See the answer with Pro.

Don't just read it. Drill it.

Reconstruct Ransom Note from memory until it sticks. AlgoDrill blanks out key lines and makes you fill them back in, step by step.

Unlock the Ransom Note drill

or drill a free problem

1	`from collections import Counter`
2
3	`class Solution:`
4	`def canConstruct(self, ransomNote: str, magazine: str) -> bool:`
5	`available_chars = Counter(magazine)`
6
7	`for char in ransomNote:`
8	`if available_chars[char] == 0:`
9	`return False`
10
11	`available_chars[char] -= 1`
12
13	`return True`