Skip to main content

383 - Ransom Note

Difficulty: Easy | Pattern: Hash Map / Counting | Company tags: Amazon, Google

Problem Statement​

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 in ransomNote.

Example 1:

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

Example 2:

Input: ransomNote = "aa", magazine = "ab"
Output: false

Example 3:

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

Algorithm Flow​

Approach: Character Counting — O(n)​

Key insight: Count how many of each letter the magazine has. Then check if the ransom note needs more of any letter than the magazine provides.

from collections import Counter

def canConstruct(ransomNote: str, magazine: str) -> bool:
    magazine_count = Counter(magazine)
    
    for c in ransomNote:
        magazine_count[c] -= 1
        if magazine_count[c] < 0:
            return False
    
    return True

Or using Counter subtraction:

def canConstruct(ransomNote: str, magazine: str) -> bool:
    return not (Counter(ransomNote) - Counter(magazine))

Counter subtraction keeps only positive counts — if any character in ransomNote appears more times than in magazine, it will remain in the result (non-empty = False).

Alternative: Array (26 characters)​

def canConstruct(ransomNote: str, magazine: str) -> bool:
    count = [0] * 26
    for c in magazine:
        count[ord(c) - ord('a')] += 1
    for c in ransomNote:
        count[ord(c) - ord('a')] -= 1
        if count[ord(c) - ord('a')] < 0:
            return False
    return True

Edge Cases​

  • ransomNote = "" → True (empty note can always be constructed)
  • magazine = "" → False (unless ransomNote is also empty)
  • More letters needed than available → False (early exit)

Complexity​

  • Time: O(m + n) where m = len(magazine), n = len(ransomNote)
  • Space: O(1) — at most 26 distinct lowercase letters

Note: This is essentially the same problem as 242 (Valid Anagram) but with an asymmetric constraint — magazine must provide enough letters, but magazine can have extra.

Key Terms​

TermDefinition
Hash map countingStoring character frequencies in a hash map (or Counter) to compare availability against demand.
Frequency arrayA fixed-size array (26 for lowercase letters) used instead of a hash map for O(1) space and faster constant factors.
Asymmetric constraintA rule where one side (magazine) may have surplus but the other (ransomNote) may not exceed it — unlike Valid Anagram's exact-match constraint.
Early exitReturning False as soon as a letter's count goes negative, avoiding unnecessary further scanning.

FAQ​

Q: Can this be solved without extra space? A: Not truly O(1) extra space if input isn't limited to a fixed alphabet, but with only lowercase English letters, the 26-length array is effectively constant space regardless of input size.

Q: What if ransomNote is empty? A: Return True immediately — an empty string requires no letters and is trivially constructible.

Q: What if magazine is empty but ransomNote is not? A: Return False, since there are no letters available to draw from.

Q: How would this change if letters could be reused unlimited times from magazine? A: The problem would reduce to a simple set-containment check: every character in ransomNote must exist somewhere in magazine, with no counting needed.

Q: How does this differ from Valid Anagram (242)? A: Valid Anagram requires both strings to have identical character counts (exact match), while Ransom Note only requires magazine's counts to be greater than or equal to ransomNote's — magazine can have leftover letters.

Quick Revision​

  • Goal: check if ransomNote can be built from magazine's letters, each used at most once.
  • Count magazine's letters first (Counter or 26-length array).
  • Walk ransomNote, decrementing counts; if any count goes negative, return False immediately.
  • If the full scan completes without going negative, return True.
  • Time: O(m + n); Space: O(1) since alphabet size is fixed at 26.
  • Related to 242 (Valid Anagram) but with an asymmetric "at least" constraint instead of exact equality.
  • Edge cases: empty ransomNote → True; empty magazine with non-empty ransomNote → False.
  • 242 - Valid Anagram — same counting technique with an exact-match constraint instead of asymmetric.
  • Group Anagrams — uses character-count/sorted-string signatures built from the same counting idea.
  • 387 - First Unique Character in a String — another single-pass character-frequency problem.