Algocademy Logo

Course Outline

Ransom Note in C++ with O(n + m) Time Complexity


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.


Understanding the Problem

The core challenge of this problem is to determine if the characters in the ransomNote can be found in the magazine string, considering that each character in the magazine can only be used once. This problem is significant in scenarios where resource allocation or availability needs to be checked, such as in inventory management or text processing.

Approach

To solve this problem, we can use a hash map (or an array in this case, since we are dealing with characters) to count the frequency of each character in both the ransomNote and the magazine. The steps are as follows:

  1. Initialize an array to count the frequency of each character in the magazine.
  2. Iterate through the magazine and populate the frequency array.
  3. Iterate through the ransomNote and decrement the frequency of each character in the array.
  4. If at any point the frequency of a character in the array is less than zero, return false.
  5. If the loop completes without issues, return true.

Algorithm

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

  1. Create an array charCount of size 26 (for each letter in the alphabet) initialized to zero.
  2. Iterate through the magazine string and increment the corresponding index in charCount for each character.
  3. Iterate through the ransomNote string and decrement the corresponding index in charCount for each character.
  4. If any index in charCount goes below zero during the decrement step, return false.
  5. If the loop completes, return true.

Code Implementation


#include <iostream>
#include <string>
#include <vector>

using namespace std;

bool canConstruct(string ransomNote, string magazine) {
    // Array to store the frequency of each character in the magazine
    vector<int> charCount(26, 0);

    // Populate the frequency array with characters from the magazine
    for (char c : magazine) {
        charCount[c - 'a']++;
    }

    // Check if ransomNote can be constructed from magazine
    for (char c : ransomNote) {
        if (--charCount[c - 'a'] < 0) {
            return false;
        }
    }

    return true;
}

int main() {
    string ransomNote1 = "aa";
    string magazine1 = "abb";
    cout << (canConstruct(ransomNote1, magazine1) ? "true" : "false") << endl; // Output: false

    string ransomNote2 = "aa";
    string magazine2 = "aab";
    cout << (canConstruct(ransomNote2, magazine2) ? "true" : "false") << endl; // Output: true

    return 0;
}

Complexity Analysis

The time complexity of this solution is O(n + m), where n is the length of the ransomNote and m is the length of the magazine. This is because we iterate through both strings once. The space complexity is O(Σ), where Σ is the size of the character set (in this case, 26 for lowercase English letters).

Edge Cases

Potential edge cases include:

  • Empty ransomNote: Should return true as no characters are needed.
  • Empty magazine with non-empty ransomNote: Should return false.
  • Characters in ransomNote not present in magazine: Should return false.

Testing

To test the solution comprehensively, consider the following test cases:

ransomNote = "", magazine = ""  // Output: true
ransomNote = "a", magazine = ""  // Output: false
ransomNote = "", magazine = "a"  // Output: true
ransomNote = "a", magazine = "a"  // Output: true
ransomNote = "aa", magazine = "a"  // Output: false
ransomNote = "aa", magazine = "aab"  // Output: true

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 a hash map approach in C++. We covered 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: