leetcode-150

Ransom Note

The Ransom Note problem is a popular string problem found in coding interviews. It tests your ability to count characters and manage constraints under simple rules. While the problem is conceptually easy, it reveals how well you understand hashing, maps, and character frequency management.

Let’s walk through the problem, the thinking process, and a clean JavaScript solution that makes it crystal clear.

---

🔍 Problem Statement

Given two strings ransomNote and magazine, return true if ransomNote can be constructed by using the letters from magazine, and false otherwise.

Note:

• Each letter in magazine can only be used once.

Examples:

canConstruct("a", "b");         // false
canConstruct("aa", "ab");       // false
canConstruct("aa", "aab");      // true

---

🧠 Core Idea

To solve this, we just need to make sure that for each character in the ransomNote, the magazine has at least that many of that character.

The simplest way? Count the characters in magazine, then loop through ransomNote and reduce the count as we use them. If at any point a character is not available or runs out, return false.

---

✅ JavaScript Solution using a Frequency Map

/**
 * Determines if the ransomNote can be constructed from the magazine.
 * @param {string} ransomNote
 * @param {string} magazine
 * @return {boolean}
 */
var canConstruct = function(ransomNote, magazine) {
    const freq = {};

    for (const char of magazine) {
        freq[char] = (freq[char] || 0) + 1;
    }

    for (const char of ransomNote) {
        if (!freq[char]) return false;
        freq[char]--;
    }

    return true;
};

How it works:

• Build a frequency object for all characters in magazine.
• Loop over ransomNote, and for each character:
  • If the character is not present or used up, return false.
  • Otherwise, decrement its count.
• If you finish the loop, return true.

---

🚫 Common Pitfalls

• ❌ Forgetting that each letter can only be used once.
• ❌ Trying to sort strings and match substrings (inefficient and unnecessary).
• ❌ Modifying strings directly — remember, strings are immutable in JavaScript.

---

🧩 Optimization Notes

• Time complexity: O(m + n), where m is the length of magazine, n is the length of ransomNote.
• Space complexity: O(1) because the character set is limited to lowercase letters (max 26).

This makes it a fast and efficient solution, perfect for coding rounds.

---

🧠 Final Thoughts

The Ransom Note problem is a great way to practice building frequency maps and thinking in terms of resource allocation. It’s also a good precursor to more complex problems involving hash maps and greedy algorithms.

Try this with different character sets (like Unicode), or extend it to word-level logic for a fun twist!

---

🔗 Reference

LeetCode: Ransom Note

This site is open source. Improve this page.