LeetCode Challenge: 383. Ransom Note - JavaScript Solution 🚀

#javascript #programming #leetcode #interview

Top Interview 150

The Ransom Note problem is a simple string manipulation challenge that tests your ability to manage character counts efficiently. Let’s solve LeetCode 383 step by step.

🚀 Problem Description

Given two strings ransomNote and magazine:

Return true if ransomNote can be constructed using letters from magazine.
Each letter in magazine can only be used once in ransomNote.

💡 Examples

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

🏆 JavaScript Solution

We solve this problem by counting the occurrences of each letter in magazine and comparing them with the required counts for ransomNote.

Implementation

var canConstruct = function(ransomNote, magazine) {
    const charCount = {};

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

    for (let char of ransomNote) {
        if (!charCount[char] || charCount[char] <= 0) {
            return false;
        }
        charCount[char]--;
    }

    return true;
};

🔍 How It Works

Count Characters in Magazine:
- Create a hash map (charCount) to store the frequency of each character in magazine.
Validate Against Ransom Note:
- Iterate through each character in ransomNote.
- Check if the character is available in charCount.
- If not, return false.
- Decrement the count of the character in charCount.
Return Result:
- If all characters are found with sufficient counts, return true.

🔑 Complexity Analysis

Time Complexity: O(n+m), where n is the length of magazine and m is the length of ransomNote.
- Counting characters in magazine takes O(n).
- Validating ransomNote takes O(m).
Space Complexity: O(k), where k is the number of unique characters in magazine.

📋 Dry Run

Input: ransomNote = "aa", magazine = "aab"

Output: true

✨ Pro Tips for Interviews

Clarify Constraints:
- Ensure that ransomNote and magazine only contain lowercase letters.
- Ask about edge cases, such as empty strings.
Discuss Optimizations:
- Highlight how using a hash map ensures efficient character counting.
Edge Cases:
- ransomNote longer than magazine → immediately return false.
- All characters in magazine but insufficient counts.