Start learning free

LESSON 257 OF 410 · HASH TABLE

Ransom Note in O(n + m) Time Complexity using JavaScript

Practice O(n + m) Read the full explanation

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

Each letter in magazine can only be used once in ransomNote.

Example 1:

Input:  ransomNote = "aa", magazine = "abb"
Output:  false

Example 2:

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

Note:

Your algorithm should run in O(n + m) time and use O(Σ) extra space.


Hints:

Let's take the two examples given in the statement and solve them "by hand". In both examples, ransomNote consists of two 'a's. Which means we need to have at least two 'a's in magazine to be able to construct the solution. In the first example, we have only one 'a' in magazine and that's why we return false while in the second example, we have two of them, so that's why we return true. Pretty simple. Now what if ransomNote also contains letter 'b'? What property should be satisfied to return true? Take some small examples on paper and try to figure it out.

Let's take ransomNote = "abba". We need at least two 'a's and two 'b's in magazine to be able to construct the solution. First observation is that the order of letters in ransomNote is not important. The requirement is the same also for ransomNote = "aabb" or ransomNote = "abba". The same holds true for magazine. It doesn't matter if magazine = "aaabbb" or magazine = "ababab", both are good as the conditions are satisfied:
  • 'a' occurs in magazine at least the same number of times it does in ransomNote (3 >= 2)
  • 'b' occurs in magazine at least the same number of times it does in ransomNote (3 >= 2)
All these being said, can you figure out what condition should be satisfied to return true for the general case?

The condition is that for each letter of the alphabet (from 'a' to 'z'), the letter should appear in magazine at least the same number of times it does in ransomNote. So we need to separately count the number of occurrences of each letter in magazine and in ransomNote. How can we achieve this?

We have a data structure specially designed to do that: a frequency table, such as a Hash Map (or, since the letters are only 'a' to 'z', a 26-slot array). We can build two frequency tables:
  • one for ransomNote, where the entry for letter c is the number of occurrences of c in ransomNote
  • one for magazine, where the entry for letter c is the number of occurrences of c in magazine
How should we populate these tables?

Using a loop, we will go through every character c of ransomNote and increment the entry for c in its table. We will do the same for magazine. What should we do after we have populated these tables?

Using a loop, we should go through each character c of the alphabet (from 'a' to 'z') and check if the count of c in ransomNote is greater than its count in magazine. If so, we should return false. When this loop terminates, we can conclude that the solution is valid, so we can return true

STEP 1 OF 9
    Ctrl + Enter to check

    JAVASCRIPT · HASH TABLE

    Ransom Note in JavaScript, explained

    Problem Definition

    The problem requires us to determine if we can construct the string ransomNote using the characters from the string magazine. Each character in magazine can only be used once.

    Input:

    • ransomNote: A string representing the ransom note.
    • magazine: A string representing the magazine text.

    Output:

    • Return true if ransomNote can be constructed from magazine, otherwise return false.

    Constraints:

    • Both strings consist of lowercase English letters.

    Example:

    Input:  ransomNote = "aa", magazine = "abb"
Output:  false

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

    Understanding the Problem

    The core challenge is to ensure that every character in ransomNote appears in magazine at least as many times as it does in ransomNote. This problem is significant in scenarios where resource allocation or availability needs to be checked, such as in inventory management or text processing.

    Potential Pitfalls:

    • Assuming characters can be reused without checking their counts.
    • Not considering edge cases where ransomNote is longer than magazine.

    Approach

    To solve this problem, we can use a hash map (or object in JavaScript) to count the occurrences of each character in both ransomNote and magazine. We then compare these counts to determine if ransomNote can be constructed.

    Naive Solution:

    A naive solution would involve checking each character of ransomNote against magazine repeatedly, which would be inefficient with a time complexity of O(n * m).

    Optimized Solution:

    We can optimize this by using hash maps to store character counts, resulting in a time complexity of O(n + m).

    Steps:

    1. Initialize two hash maps to store character counts for ransomNote and magazine.
    2. Populate the hash maps by iterating through each string.
    3. Compare the counts in both hash maps to determine if ransomNote can be constructed.

    Algorithm

    Here is a step-by-step breakdown of the algorithm:

    1. Create two hash maps: ransomFreq and magazineFreq.
    2. Iterate through ransomNote and populate ransomFreq.
    3. Iterate through magazine and populate magazineFreq.
    4. For each character in ransomNote, check if its count in magazineFreq is at least as much as in ransomFreq.
    5. If any character's count in magazineFreq is less, return false.
    6. If all checks pass, return true.

    Code Implementation

    // Function to determine if ransomNote can be constructed from magazine
function canConstruct(ransomNote, magazine) {
  // Create hash maps to store character counts
  const ransomFreq = {};
  const magazineFreq = {};

  // Populate ransomFreq with counts from ransomNote
  for (let char of ransomNote) {
    ransomFreq[char] = (ransomFreq[char] || 0) + 1;
  }

  // Populate magazineFreq with counts from magazine
  for (let char of magazine) {
    magazineFreq[char] = (magazineFreq[char] || 0) + 1;
  }

  // Check if ransomNote can be constructed from magazine
  for (let char of ransomNote) {
    if (!magazineFreq[char] || ransomFreq[char] > magazineFreq[char]) {
      return false;
    }
  }

  return true;
}

// Example usage
console.log(canConstruct("aa", "abb")); // Output: false
console.log(canConstruct("aa", "aab")); // Output: true

    Complexity Analysis

    The time complexity of this solution is O(n + m), where n is the length of ransomNote and m is the length of magazine. This is because we iterate through each string once to populate the hash maps and then iterate through ransomNote again for the final check.

    The space complexity is O(Σ), where Σ is the number of unique characters in the input strings. This is due to the storage required for the hash maps.

    Edge Cases

    Consider the following edge cases:

    • ransomNote is empty: The function should return true.
    • magazine is empty but ransomNote is not: The function should return false.
    • Both ransomNote and magazine are empty: The function should return true.

    Testing Edge Cases:

    // Edge case tests
console.log(canConstruct("", "")); // Output: true
console.log(canConstruct("a", "")); // Output: false
console.log(canConstruct("", "a")); // Output: true

    Testing

    To test the solution comprehensively, consider a variety of test cases:

    • Simple cases with short strings.
    • Cases where ransomNote is longer than magazine.
    • Cases with repeated characters.
    • Edge cases as discussed above.

    Example Test Cases:

    // Example test cases
console.log(canConstruct("aa", "abb")); // Output: false
console.log(canConstruct("aa", "aab")); // Output: true
console.log(canConstruct("abc", "aabbcc")); // Output: true
console.log(canConstruct("abc", "ab")); // Output: false

    Thinking and Problem-Solving Tips

    When approaching such problems, consider the following tips:

    • Break down the problem into smaller, manageable parts.
    • Use appropriate data structures to simplify the solution.
    • Think about edge cases and how your solution handles them.
    • Practice similar problems to improve your problem-solving skills.

    Conclusion

    In this blog post, we discussed how to solve the "Ransom Note" problem using an efficient algorithm with a time complexity of O(n + m). We explored the problem definition, approach, algorithm, code implementation, complexity analysis, edge cases, and testing. Understanding and solving such problems is crucial for developing strong problem-solving skills in programming.

    Additional Resources

    For further reading and practice, consider the following resources:

    Keep going with JavaScriptAbout 340 step-by-step lessons, from your first line of code to coding interviews. Free to start.
    Start learning free