We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Ransom Note

Number: 383

Difficulty: Easy

Paid? No

Companies: Microsoft, Meta, Karat, Amazon, Bloomberg, Google, Disney, Apple, Adobe, Criteo

Problem Description

Given two strings ransomNote and magazine, determine whether ransomNote can be constructed using the letters from magazine. Each letter in magazine can only be used once.

Key Insights

  • Use a hash table (or dictionary) to store the frequency of each character present in magazine.
  • Iterate over every character in ransomNote and check if the corresponding count in the hash table is available and sufficient.
  • Decrease the character count for every match; if any character count falls below zero, return false.
  • If all characters in ransomNote can be accounted for, return true.

Space and Time Complexity

Time Complexity: O(n + m), where n is the length of magazine and m is the length of ransomNote. Space Complexity: O(1), since the extra space required for the hash table is limited to at most 26 entries for lowercase English letters.

Solution

We construct a frequency map for the magazine string using a hash table. This frequency map records how many times each letter appears in magazine. Then we iterate through the ransomNote string, and for every letter, we check the corresponding frequency in the map. If a letter is not found or its frequency is zero, we immediately return false as it means the letter cannot be used to build the note. Otherwise, we decrement the frequency count by one. If we successfully process all characters in ransomNote, then it can be constructed from magazine, and we return true.

Code Solutions

# Function to check if ransom note can be constructed from magazine
def canConstruct(ransomNote: str, magazine: str) -> bool:
    # Create a dictionary to hold the frequency of each character in magazine
    char_frequency = {}
    for char in magazine:
        char_frequency[char] = char_frequency.get(char, 0) + 1

    # Check each character in ransomNote against the frequency map
    for char in ransomNote:
        if char_frequency.get(char, 0) == 0:
            return False  # Character not available or used up
        char_frequency[char] -= 1  # Use the character

    return True

# Example usage:
if __name__ == "__main__":
    print(canConstruct("aa", "aab"))  # Expected output: True
← Back to All Questions