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

1. Count Characters in Magazine:

   • Create a hash map (charCount) to store the frequency of each character in magazine.

2. 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.

3. 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

1. Clarify Constraints:

   • Ensure that ransomNote and magazine only contain lowercase letters.
   • Ask about edge cases, such as empty strings.

2. Discuss Optimizations:

   • Highlight how using a hash map ensures efficient character counting.

3. Edge Cases:

   • ransomNote longer than magazine → immediately return false.
   • All characters in magazine but insufficient counts.

📚 Learn More

Check out the full explanation and code walkthrough on my previous Dev.to post:
👉 Set Matrix Zeroes - JavaScript Solution

What’s your preferred method to solve this problem? Let’s discuss! 🚀