Ransom Note easy

Problem Statement

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 = "a", magazine = "b" Output: false

Example 2:

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

Steps

1. Create a frequency map: We'll use a hash map (unordered_map in C++) to store the frequency of each character in the magazine string. This allows for efficient lookup of character counts.

2. Check ransomNote characters: Iterate through each character in the ransomNote string.

3. Verify character availability: For each character in ransomNote, check if it exists in the frequency map and if its frequency is greater than 0.

4. Decrement frequency: If the character is found and its frequency is positive, decrement its frequency in the map.

5. Handle missing characters: If a character from ransomNote is not found in the map or its frequency is 0, it means we cannot construct the ransomNote and we return false.

6. Return true: If the loop completes without finding any missing or insufficient characters, it means we can construct the ransomNote using characters from magazine, so we return true.

Explanation

The solution uses a hash map to efficiently track the character counts in the magazine. This approach avoids repeatedly searching the magazine string for each character in the ransomNote. The time complexity is dominated by the iterations through the strings, making it linear in the combined length of the input strings.

Code

#include <iostream>
#include <string>
#include <unordered_map>

using namespace std;

bool canConstruct(string ransomNote, string magazine) {
    unordered_map<char, int> magFreq;

    // Create frequency map for magazine
    for (char c : magazine) {
        magFreq[c]++;
    }

    // Check ransomNote characters against frequency map
    for (char c : ransomNote) {
        if (magFreq.count(c) == 0 || magFreq[c] == 0) {
            return false; // Character not found or frequency is 0
        }
        magFreq[c]--;
    }

    return true; // All characters found and sufficient
}

int main() {
    string ransomNote1 = "a";
    string magazine1 = "b";
    cout << "Example 1: " << canConstruct(ransomNote1, magazine1) << endl; // Output: false

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

    string ransomNote3 = "aa";
    string magazine3 = "aba";
    cout << "Example 3: " << canConstruct(ransomNote3, magazine3) << endl; // Output: true

    return 0;
}

Complexity

• Time Complexity: O(m + n), where 'm' is the length of ransomNote and 'n' is the length of magazine. We iterate through both strings once.
• Space Complexity: O(k), where 'k' is the number of unique characters in magazine. This is the space used by the hash map. In the worst case, k could be the length of the magazine, but it's often much smaller.