Algocademy Logo

Course Outline

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


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.


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: