algoadvance

Leetcode 383. Ransom Note

Problem Statement

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

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

Example 1:

Example 2:

Example 3:

Clarifying Questions

  1. Can the ransom note and magazine contain characters other than lowercase English letters?
    • According to the problem, both ransomNote and magazine consist of lowercase English letters only.
  2. What should be returned if either ransomNote or magazine is empty?
    • If ransomNote is empty, the return value should be true because an empty note can always be constructed.
    • If magazine is empty and ransomNote is not, the return value should be false.

Strategy

  1. Create a frequency count for each letter in magazine using an array or a hash map.
  2. Iterate over each character in ransomNote and decrease the frequency count from the magazine’s frequency map.
  3. If at any point the frequency of any letter in magazine goes below zero, return false.
  4. If all characters in ransomNote can be matched with characters in magazine, return true.

Time Complexity

Code

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

bool canConstruct(std::string ransomNote, std::string magazine) {
    std::unordered_map<char, int> letterCount;
    
    // Build the letter frequency map from the magazine
    for (char c : magazine) {
        letterCount[c]++;
    }
    
    // Check if ransom note can be constructed
    for (char c : ransomNote) {
        if (letterCount[c] == 0) {
            return false;
        }
        letterCount[c]--;
    }
    
    return true;
}

int main() {
    std::string ransomNote = "a";
    std::string magazine = "b";
    std::cout << std::boolalpha << canConstruct(ransomNote, magazine) << std::endl; // Output: false
    
    ransomNote = "aa";
    magazine = "ab";
    std::cout << std::boolalpha << canConstruct(ransomNote, magazine) << std::endl; // Output: false
    
    ransomNote = "aa";
    magazine = "aab";
    std::cout << std::boolalpha << canConstruct(ransomNote, magazine) << std::endl; // Output: true

    return 0;
}

This code implements the described strategy to determine if the ransomNote can be constructed from the magazine. It uses an unordered map to keep track of the character count in the magazine and then checks if those counts suffice to form the ransom note.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI