Leetcode 383: Ransom Note

Input: The input consists of two strings, ransomNote and magazine.

Example: ransomNote = 'hello', magazine = 'ohelloll'

Constraints:

• 1 <= ransomNote.length, magazine.length <= 10^5

• ransomNote and magazine consist of lowercase English letters.

Output: Return a boolean value: true if ransomNote can be constructed from the letters in magazine, false otherwise.

Example: Output: true for ransomNote = 'hello' and magazine = 'ohelloll'

Constraints:

• The result should be a boolean indicating whether it's possible to construct ransomNote from magazine.

Goal: The goal is to verify if each letter in ransomNote appears enough times in magazine.

Steps:

• Create a frequency map for characters in the magazine.

• Iterate over the ransomNote string and check if each character is available in the magazine's frequency map.

• If any character in ransomNote is missing or insufficient in magazine, return false.

• If all characters are found with sufficient frequency, return true.

Goal: Ensure the solution is efficient and works within the problem's constraints.

Steps:

• The time complexity should be linear with respect to the length of the strings.

• The space complexity should be proportional to the number of unique characters in the magazine.

Assumptions:

• Both ransomNote and magazine are non-empty strings.

• There are no special characters, only lowercase English letters.

• Input: ransomNote = 'g', magazine = 'h'

• Explanation: In this case, the letter 'g' is not present in the magazine, so the answer is false.

• Input: ransomNote = 'gg', magazine = 'g'

• Explanation: Here, the letter 'g' appears only once in the magazine, so it's impossible to construct the ransomNote, and the answer is false.

• Input: ransomNote = 'hello', magazine = 'ohelloll'

• Explanation: In this case, all letters in ransomNote are available in magazine in sufficient quantities, so the answer is true.

Approach: The approach involves counting the frequency of characters in the magazine and then verifying if those frequencies are sufficient for constructing the ransomNote.

Observations:

• The problem requires checking character availability in a string.

• Using a frequency map for the magazine allows us to efficiently check if the ransomNote can be constructed.

Steps:

• Create a map to store the frequency of characters in the magazine.

• For each character in the ransomNote, check if it exists in the frequency map with a sufficient count.

• If any character is missing or insufficient, return false.

• If all characters are available, return true.

Empty Inputs:

• Both ransomNote and magazine are non-empty as per the constraints.

Large Inputs:

• The solution must handle the case where the length of ransomNote and magazine is up to 10^5 efficiently.

Special Values:

• Ensure that the solution works for edge cases where the magazine has exactly the required number of letters or where ransomNote and magazine are identical.

Constraints:

• The solution should be linear in time complexity, i.e., O(n + m), where n is the length of ransomNote and m is the length of magazine.

bool canConstruct(string ransomNote, string magazine) {
    map<char, int> mp;
    for(int x: magazine)
        mp[x]++;
    
    for(int j = 0; j < ransomNote.size(); j++) {
        if(!mp.count(ransomNote[j])) return false;
        else {
            mp[ransomNote[j]]--;
            if(mp[ransomNote[j]] == 0) mp.erase(ransomNote[j]);
        }
    }
    return true;
}

1 : Function Definition

bool canConstruct(string ransomNote, string magazine) {

This line defines the function `canConstruct`, which takes two string arguments: `ransomNote` and `magazine`. It returns a boolean value indicating if the ransom note can be constructed using characters from the magazine.

2 : Map Initialization

    map<char, int> mp;

A map `mp` is created to store the frequency of each character in the `magazine` string, with characters as keys and their respective counts as values.

3 : Iterating Through Magazine

    for(int x: magazine)

This `for` loop iterates over each character `x` in the `magazine` string.

4 : Updating Frequency Map

        mp[x]++;

For each character `x` in the `magazine`, its count in the map `mp` is incremented by 1.

5 : Iterating Through Ransom Note

    for(int j = 0; j < ransomNote.size(); j++) {

This `for` loop iterates through each character in the `ransomNote` string.

6 : Checking Character Availability

        if(!mp.count(ransomNote[j])) return false;

This condition checks if the current character in the `ransomNote` is not present in the map `mp`. If it's not found, the function returns `false`, indicating that the ransom note cannot be constructed.

7 : Character Removal

        else {

If the character is found in the map `mp`, the function proceeds to reduce its count.

8 : Decrementing Character Count

            mp[ransomNote[j]]--;

The count of the current character in `ransomNote` is decremented by 1 in the map `mp`.

9 : Removing Zero Counted Characters

            if(mp[ransomNote[j]] == 0) mp.erase(ransomNote[j]);

If the count of the current character in the map reaches 0, the character is erased from the map to save space.

10 : End of Ransom Note Loop

This marks the end of the loop that iterates through the `ransomNote` string.

11 : Return Statement

    return true;

If the loop completes without returning `false`, it means the ransom note can be constructed, so the function returns `true`.

Best Case: O(n + m)

Average Case: O(n + m)

Worst Case: O(n + m)

Description: The time complexity is linear with respect to the lengths of the ransomNote and magazine.

Best Case: O(k)

Worst Case: O(k)

Description: The space complexity depends on the number of unique characters in the magazine, which is at most 26 for lowercase English letters.

Leetcode 383: Ransom Note

Solution to LeetCode 383: Ransom Note Problem

Explore →