Ransom Note

LeetCode 383 | Difficulty: Easy

Easy

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 <= 10^5`

- `ransomNote` and `magazine` consist of lowercase English letters.

Topics: Hash Table, String, Counting

---

Approach

Hash Map

Use a hash map for O(1) average lookups. Store seen values, frequencies, or indices. The key question: what should I store as key, and what as value?

When to use

Need fast lookups, counting frequencies, finding complements/pairs.

String Processing

Consider character frequency counts, two-pointer approaches, or building strings efficiently. For pattern matching, think about KMP or rolling hash. For palindromes, expand from center or use DP.

When to use

Anagram detection, palindrome checking, string transformation, pattern matching.

---

Solutions

Solution 1: C# (Best: 116 ms)

Metric	Value
Runtime	116 ms
Memory	N/A
Date	2018-04-05

Solution

public class Solution {
    public bool CanConstruct(string ransomNote, string magazine) {
        Dictionary<char,int> mag = new Dictionary<char, int>();
    for (int i = 0; i < magazine.Length; i++)
    {
        if(mag.ContainsKey(magazine[i]))
        {
            mag[magazine[i]]++;
        }
        else
        {
            mag.Add(magazine[i],1);
        }
    }
    
    for (int i = 0; i < ransomNote.Length; i++)
    {
        if(mag.ContainsKey(ransomNote[i]))
        {
            if(mag[ransomNote[i]]<=0)
            {
                return false;
            }
            else
            {
                mag[ransomNote[i]]--;
            }
        }
        else
        {
            return false;
        }
    }
    return true;
    }
}

---

Complexity Analysis

Approach	Time	Space
Hash Map	$O(n)$	$O(n)$

---

Interview Tips

Key Points

• Start by clarifying edge cases: empty input, single element, all duplicates.
• Hash map gives O(1) lookup — think about what to use as key vs value.