383. Ransom Note - Detailed Explanation

Problem Statement

Given two strings, ransomNote and magazine, determine if you can construct the ransomNote by cutting out letters from the magazine. Each letter in the magazine can only be used once. Return true if it’s possible, otherwise false.

Examples

Example 1

Input: ransomNote = "a", magazine = "b"  
Output: false  
Explanation: You cannot construct "a" from "b".  

Example 2

Input: ransomNote = "aa", magazine = "ab"  
Output: false  
Explanation: You need two 'a's but magazine has only one.  

Example 3

Input: ransomNote = "aa", magazine = "aab"  
Output: true  
Explanation: You can use the two 'a's from magazine.  

Constraints

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

Hints

1. You only need to check that every character in the ransom note appears at least as many times in the magazine.
2. Can you count letters in the magazine first, then “spend” them as you scan the ransom note?
3. Since the alphabet size is fixed (26 letters), a simple array of length 26 can track counts in O(1) per letter.

Approach 1 – Counting Array

Explanation

Use an integer array count[26] to tally how many times each letter appears in the magazine. Then iterate through each character of the ransom note:

• Convert character to index i = ch − 'a'.
• Decrement count[i].
• If count[i] becomes negative, you’ve tried to use a letter more times than the magazine provides → return false.
  If you finish without running out of any letter, return true.

Step‑by‑Step

1. Initialize count[0…25] = 0.
2. For each ch in magazine, do count[ch−'a']++.
3. For each ch in ransomNote, do:
   • idx = ch − 'a'
   • count[idx]––
   • If count[idx] < 0, return false.
4. Return true.

Complexity

• Time: O(m + n), where m = magazine length, n = ransomNote length
• Space: O(1) (26‑element array)

Approach 2 – Hash Map (Generalized)

Explanation

If the character set weren’t limited to lowercase letters, use a hash map Map<char,int> to count magazine letters. The logic is identical: build counts, then decrement for each ransom‑note letter, checking for shortages.

Complexity

• Time: O(m + n)
• Space: O(σ), where σ = size of the character set

Python Code