DEV Community

Cover image for LeetCode Challenge: 383. Ransom Note - JavaScript Solution ๐Ÿš€
Rahul Kumar Barnwal
Rahul Kumar Barnwal

Posted on

2 1 1 1 1

LeetCode Challenge: 383. Ransom Note - JavaScript Solution ๐Ÿš€

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
Enter fullscreen mode Exit fullscreen mode

Example 2

Input: ransomNote = "aa", magazine = "ab"  
Output: false
Enter fullscreen mode Exit fullscreen mode

Example 3

Input: ransomNote = "aa", magazine = "aab"  
Output: true
Enter fullscreen mode Exit fullscreen mode

๐Ÿ† 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;
};
Enter fullscreen mode Exit fullscreen mode

๐Ÿ” 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"
Dry RUn

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! ๐Ÿš€


Study

Top comments (1)

Collapse
 
rahulgithubweb profile image
Rahul Kumar Barnwal โ€ข

Follow Me on GitHub ๐Ÿš€

If you found this solution helpful, check out more of my projects and solutions on my GitHub profile.

Don't forget to follow for more updates!

Sentry image

See why 4M developers consider Sentry, โ€œnot bad.โ€

Fixing code doesnโ€™t have to be the worst part of your day. Learn how Sentry can help.

Learn more