💬 Discord
Sign In
NeetCode #70LC-383EasyArrays & Hashing
← Back to All Problems

#70 · #383 · Ransom Note(赎金信)

📌 Problem Statement & Constraints

Given two strings ransomNote and magazine, return true if ransomNote can be constructed using the letters of magazine, each used at most once. Constraints: 1 <= ransomNote.length, magazine.length <= 10^5, all lowercase letters.

💡 Core Algorithmic Approaches

  1. Count the letters available in magazine.
  2. Walk through ransomNote, decrementing the available count for each required letter.
  3. If any letter's count would drop below zero, the note cannot be built.
  4. This is the classic multiplicity-aware membership test; a set comparison would be insufficient.

💻 Benchmark Python3 Implementation

class Solution:
    def canConstruct(self, ransomNote: str, magazine: str) -> bool:
        from collections import Counter
        avail = Counter(magazine)
        for ch in ransomNote:
            if avail[ch] == 0:
                return False           # letter exhausted or absent
            avail[ch] -= 1
        return True


# Compact equivalent using Counter subtraction
class Solution2:
    def canConstruct(self, ransomNote: str, magazine: str) -> bool:
        from collections import Counter
        return not (Counter(ransomNote) - Counter(magazine))

⚡ Complexity Deep Dive

⏱️ Time Complexity
O(m + n): one pass over each string.
💾 Space Complexity
O(k) for the counter, with k <= 26, so O(1) in terms of the alphabet.

⚠️ Interview Pitfalls & Follow-ups

  • Using set(ransomNote) <= set(magazine): this ignores multiplicity, so magazine = "a" would wrongly allow ransomNote = "aa".
  • Iterating magazine instead of ransomNote: you must verify that every needed letter is available, not the other way round.
  • Forgetting the length check: it is not needed here, since the counter approach already catches the case, but an early len(ransomNote) > len(magazine) exit is a cheap optimisation.