LeetCode 383. Ransom Note | Hash Map Solution in JavaScript

📌 Introduction

In this post, we’ll solve LeetCode 383. Ransom Note. We’ll cover a frequency map approach, and analyze the time and space complexities. Code examples will be in JavaScript, with step-by-step explanations.

👉 Original problem link: LeetCode – Ransom Note

---

1. Problem Overview

The problem asks whether a ransomNote string can be created using the characters from a magazine string. Each character from magazine can only be used once.

---

2. Example

Input: ransomNote = "aa", magazine = "aab" Output: true Explanation: The magazine contains two 'a's and one 'b', which is sufficient to construct the ransomNote "aa".

---

3. Approaches

🔹 Optimized Approach

• Idea:

  • Since the input strings only contain lowercase English letters, we can use a fixed-size array of 26 to store character frequencies.

  • First, iterate through the magazine string and count the frequency of each character, storing the counts in the array.

  • Then, iterate through the ransomNote string. For each character, check its frequency in the array.

  • If the frequency is 0, it means we don't have enough of that character, so we can immediately return false.

  • Otherwise, decrement the character's count in the frequency array.

  • If the loop completes without returning false, it means the ransomNote can be constructed, so we return true.

Code (JavaScript):

/**
 * @param {string} ransomNote
 * @param {string} magazine
 * @return {boolean}
 */
var canConstruct = function(ransomNote, magazine) {
    const frequency = new Array(26).fill(0)

    for(const c of magazine){
        const index = c.charCodeAt(0) - 'a'.charCodeAt(0)
        frequency[index]++
    }

    for(const c of ransomNote){
        const index = c.charCodeAt(0) - 'a'.charCodeAt(0)
        if(frequency[index] === 0) return false
        frequency[index]--
    }

    return true
};

Time Complexity = O(R+M) - where R and M are the lengths of the ransomNote and magazine strings, respectively. Space Complexity = O(1) - The space required is constant as it is a fixed-size array of 26 elements.

---

4. Key Takeaways

• ✨ When dealing with character frequency counts for a small, fixed character set (like lowercase English letters), a simple array can be more efficient than a Map or hash table.

• ✨ The charCodeAt() method can be used to convert characters to their ASCII values to calculate the correct index for the array.

• ✨ If the input included a wider range of characters (e.g., Unicode), a Map would be a better choice to handle the variable character set.