Mar 18, 2026 📖 4 min read

Last updated on Apr 2, 2026

Ransom Note — Coding Interview Walkthrough

Q: What data structure accurately tracks character availability for a Ransom Note?

A Hash Map gracefully handles dictionary mapping by tallying the exact frequencies of every available letter within the magazine source. Once mapped, you systematically subtract counts for each requested note character until verifying completion or failing at a deficiency.

Q: Can you optimize Ransom Note space complexity without a Hash Map?

Because English language challenges strictly limit inputs to 26 lowercase alphabetical characters, instantiating a standardized integer array of size 26 directly substitutes a Hash Map while strictly confining spatial requirements to a flat O(1) memory bound.

By intervu.dev

The core approach: Ransom Note is solved by counting character frequencies in O(m+n) time and O(1) space. Build a frequency map of the magazine's characters. For each character in the ransom note, decrement its count. If any count goes below zero, the magazine lacks that character and the answer is false.

Ransom Note is a classic character-frequency problem. The idea is simple, but it’s a reliable signal in interviews — it tests whether you reach for a hash map when you should, whether you short-circuit early, and whether you understand the constraint that real magazines don’t re-use letters.

Already know how to solve Ransom Note? Try a Ransom Note mock interview on Intervu →

The Problem

Given two strings ransomNote and magazine, return true if ransomNote can be constructed by using the letters from magazine, and false otherwise. Each letter in magazine can only be used once.

Example

Input: ransomNote = "aa", magazine = "aab" Output: true

What Interviewers Are Actually Testing

Skill	What Interviewers Observe
Frequency counting	Do you reach for a hash map or `Counter` without overthinking it?
Early termination	Do you bail as soon as you detect a missing letter?
Space optimization	Can you do it in one pass over `magazine`, one pass over `ransomNote`?
Edge cases	Empty strings, single character, magazine shorter than note?

Step 1: Clarifying Questions

Are characters lowercase only? Yes — you can use a 26-element array instead of a hash map.
Can magazine be shorter than ransomNote? Yes. If so, return false immediately.

Step 2: The Key Insight

Count the supply, then check the demand. Build a frequency map of letters in magazine. For each letter needed by ransomNote, decrement the count. If you ever need a letter that’s been exhausted, the note cannot be constructed.

Step 3: Optimal Strategy

If len(magazine) < len(ransomNote), return false immediately.
Build a Counter (or 26-element array) from magazine.
For each character in ransomNote: if that character’s count is 0, return false. Otherwise, decrement.
Return true.

Python Implementation

from collections import Counter

def canConstruct(ransomNote: str, magazine: str) -> bool:
    magazine_counts = Counter(magazine)

    for char in ransomNote:
        if magazine_counts[char] == 0:
            return False
        magazine_counts[char] -= 1

    return True

26-element array variant (avoids hash overhead):

def canConstruct(ransomNote: str, magazine: str) -> bool:
    counts = [0] * 26

    for char in magazine:
        counts[ord(char) - ord('a')] += 1

    for char in ransomNote:
        idx = ord(char) - ord('a')
        counts[idx] -= 1
        if counts[idx] < 0:
            return False

    return True

Time & Space Complexity

Aspect	Complexity
Time	O(n + m) — one pass over each string
Space	O(1) — at most 26 entries

Common Interview Mistakes

Skipping the early-length check. If magazine is shorter than ransomNote, return false immediately — don’t build the map.
Mutating the magazine string. Removing matched characters from a string is O(n) per deletion — avoid.
Not explaining the 26-element array optimization. For lowercase-only inputs, a fixed-size array is O(1) space and avoids hashing overhead.

What a Strong Candidate Sounds Like

“The straightforward approach is a frequency counter on magazine. I iterate through ransomNote and decrement for each character needed. If the count would go negative, the note can’t be built. Time is O(n + m), space is O(1) since we’re limited to 26 lowercase letters.”

Example Interview Dialogue

Interviewer: Can you reduce the space further?

Candidate: Since the alphabet is fixed at 26 lowercase letters, I can use a 26-element array instead of a hash map. Each index corresponds to ord(char) - ord('a'). It’s still O(1) space, but avoids hash collisions and is cache-friendlier in practice.

Interviewer: What’s the minimum length check about?

Candidate: If magazine has fewer characters than ransomNote, there’s no way to satisfy the note regardless of which characters are in it. It’s a cheap O(1) early exit before we build anything.

Valid Anagram — Same frequency-counting pattern.
Contains Duplicate — Hash set for membership testing.
Two Sum — Hash map for O(1) complement lookup.

Frequently Asked Questions

What data structure accurately tracks character availability for a Ransom Note?