Ransom Note

• Difficulty: Easy
• Topics: Hash Table, String, Counting
• Link: https://leetcode.com/problems/ransom-note/

Problem Description

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

Constraints:

• 1 <= ransomNote.length, magazine.length <= 105
• ransomNote and magazine consist of lowercase English letters.

Solution

1. Problem Deconstruction

Technical Restatement
Given two strings ransomNote and magazine, determine if there exists an injective mapping from characters in ransomNote to characters in magazine such that each character in ransomNote maps to a unique character in magazine with identical value, preserving the constraint that magazine characters have single-use semantics.

Beginner-Friendly Explanation
Imagine you’re cutting letters from a magazine to create a ransom note. You can only use each magazine letter once. The question is: do you have enough of the right letters in the magazine to spell out the entire ransom note?

Mathematical Formulation
Let $R$ = multiset of characters in ransomNote
Let $M$ = multiset of characters in magazine
Let $count_R(c)$ = frequency of character $c$ in $R$
Let $count_M(c)$ = frequency of character $c$ in $M$

The problem reduces to:

$$\forall c \in \Sigma,\ count_R(c) \leq count_M(c)$$

where $\Sigma$ is the lowercase English alphabet.

Constraint Analysis

• 1 <= ransomNote.length, magazine.length <= 1e5

  • Eliminates O(n²) solutions like nested loops
  • Suggests O(n) or O(n log n) approaches
  • Memory usage must be efficient (~O(1) or O(k) where k is alphabet size)

• Lowercase English letters only

  • Alphabet size fixed at 26 → constant space solutions viable
  • No Unicode/edge cases for character encoding
  • Enables array-based counting over hash maps

• Implicit Edge Cases

  • Empty ransomNote (always true)
  • ransomNote longer than magazine (immediately false)
  • Duplicate characters with insufficient magazine copies
  • All characters identical (e.g., “aaa” vs “aa”)

---

2. Intuition Scaffolding

Real-World Metaphor
You’re a chef (ransomNote) with a recipe requiring specific ingredient quantities. Magazine is your pantry. Can you make the dish without substituting ingredients and using each pantry item only once?

Gaming Analogy
In a crafting system, ransomNote is the item blueprint requiring specific material counts. Magazine is your inventory. The game checks if you have sufficient materials before allowing crafting.

Math Analogy
Given two vectors in 26-dimensional space (character counts), we’re checking if one vector is component-wise dominated by the other across all dimensions.

Common Pitfalls

1. Global character counting without verification - Just comparing total lengths ignores character distribution
2. Early optimization without brute force - Jumping to hash maps without considering fixed alphabet
3. Sorting both strings - O(n log n) unnecessary when O(n) exists
4. Modifying input strings - Destructive approaches break immutability principles
5. Overlooking short-circuit opportunities - Not checking length comparison first

---

3. Approach Encyclopedia

Brute Force (Character-by-Character Search)

Pseudocode:
for each char c in ransomNote:
    found = false
    for each char m in magazine:
        if m == c and m not used:
            mark m as used
            found = true
            break
    if not found:
        return false
return true

• Time Complexity: O(n × m) where n = |ransomNote|, m = |magazine|
  • Worst case: ransomNote = “aaa…”, magazine = “aaa…” → n × m operations
• Space Complexity: O(m) for usage tracking
• Visualization:

ransomNote: a a b
magazine:   a b c
            ✓   (use first 'a')
            ✗   (second 'a' not found)
            ✗   (fail early)

Sorting & Two-Pointer Approach

Pseudocode:
sort(ransomNote)    # O(n log n)
sort(magazine)      # O(m log m)

i = j = 0
while i < len(ransomNote) and j < len(magazine):
    if ransomNote[i] == magazine[j]:
        i++, j++
    else if ransomNote[i] > magazine[j]:
        j++
    else:
        return false
return i == len(ransomNote)

• Time Complexity: O(n log n + m log m) dominated by sorting
• Space Complexity: O(n + m) for sorting (or O(1) if in-place)
• Visualization:

Sorted: 
ransomNote: a a b
magazine:   a b c
            i     j
            ✓     ✓
              i     j
              ✗     → j++ 
              i       j
              ✗     → return false

Hash Map Counting (Universal Approach)

Pseudocode:
count = {}
for char in magazine:
    count[char] = count.get(char, 0) + 1

for char in ransomNote:
    if count.get(char, 0) == 0:
        return false
    count[char] -= 1
return true

• Time Complexity: O(n + m) for two passes
• Space Complexity: O(k) where k = unique chars in magazine (≤ 26)
• Derivation:
  • Magazine iteration: m operations
  • RansomNote iteration: n operations
  • Total: O(m + n) = O(max(m, n))

Fixed Array Counting (Optimal for Constraints)

Pseudocode:
count = [0] * 26
for char in magazine:
    count[ord(char) - ord('a')] += 1

for char in ransomNote:
    index = ord(char) - ord('a')
    if count[index] == 0:
        return false
    count[index] -= 1
return true

• Time Complexity: O(n + m) with better constant factors
• Space Complexity: O(1) fixed 26-element array
• Visualization:

count = [a:2, b:1, c:1, ... z:0]
ransomNote: "aab"
- 'a': count[0] = 2 → 1 ✓
- 'a': count[0] = 1 → 0 ✓  
- 'b': count[1] = 1 → 0 ✓
Success!

---

4. Code Deep Dive

def canConstruct(ransomNote: str, magazine: str) -> bool:
    # Early termination: ransomNote longer than magazine
    if len(ransomNote) > len(magazine):
        return False
    
    # Fixed-size array for 26 lowercase letters
    # Index mapping: 'a' → 0, 'b' → 1, ..., 'z' → 25
    char_counts = [0] * 26
    
    # Count magazine characters
    for char in magazine:
        char_counts[ord(char) - ord('a')] += 1
    
    # Verify ransomNote can be constructed
    for char in ransomNote:
        index = ord(char) - ord('a')
        # If character exhausted, construction impossible
        if char_counts[index] == 0:
            return False
        # Use one occurrence of this character
        char_counts[index] -= 1
    
    return True

Line-by-Line Analysis:

• Lines 3-4: Early length check handles Example 1 implicitly
• Line 7: Fixed array leverages constraint (lowercase English only)
• Lines 10-11: Magazine counting phase - O(m) time
• Lines 15-16: Character availability check - handles Example 2 (“aa” vs “ab”)
• Line 18: Decrement mimics “using” the magazine character
• Line 20: Only reached if all ransomNote characters satisfied

Edge Case Handling:

• Example 1 (“a” vs “b”): Fails at line 16 when ‘a’ count is 0
• Example 2 (“aa” vs “ab”): First ‘a’ succeeds, second ‘a’ finds count = 0
• Example 3 (“aa” vs “aab”): Both ‘a’ decrements succeed, returning true
• Empty ransomNote: Loop skipped, returns true immediately
• Identical strings: All decrements succeed, returns true

---

5. Complexity War Room

Hardware-Aware Analysis

• 26-element integer array = 104 bytes (fits in L1 cache)
• At 1e5 characters: ~200KB input data (fits in L2/L3 cache)
• Memory access pattern: sequential reads (cache-friendly)

Industry Comparison Table

Approach	Time	Space	Readability	Interview Viability
Brute Force	O(n×m)	O(m)	9/10	❌ Fails large N
Sorting	O(n log n)	O(n+m)	7/10	⚠️ Suboptimal
Hash Map	O(n+m)	O(k)	8/10	✅ Good general
Fixed Array	O(n+m)	O(1)	8/10	✅ Optimal

Complexity Derivation
Let n = |ransomNote|, m = |magazine|, k = |Σ| = 26
Fixed array approach:

• Magazine iteration: m operations × O(1) array access
• RansomNote iteration: n operations × O(1) array access
• Total: O(m + n)
• Space: O(k) = O(26) = O(1)

---

6. Pro Mode Extras

Algorithm Variants

1. Unicode Support: Replace array with hash map, complexity becomes O(n+m) time, O(k) space
2. Stream Processing: Use counters when inputs are streams (cannot rewind)
3. Parallel Counting: For enormous inputs, split magazine counting across threads

Interview Cheat Sheet

• First Mention: “Since we have lowercase English letters, I’ll use a fixed array for O(1) space”
• Edge Cases: Always check length comparison first for early termination
• Trade-offs: “Hash map is more general but array has better constants for this constraint”
• Testing Strategy: Test with (1) all identical chars, (2) magazine < ransomNote, (3) exact character match

Follow-up Questions

1. What if we could use magazine characters multiple times?
   → Becomes trivial (just check character set inclusion)

2. What if we needed to preserve character order?
   → Becomes subsequence problem (two-pointer O(n) solution)

3. What if magazine has uppercase letters?
   → Expand array to 52 elements or normalize case first

4. How would you extend this to words instead of characters?
   → Same algorithm with word frequencies instead of character counts