Ransom Note

Problem

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

Examples

The brute-force approach

For each character in the ransom note, scan through the remaining magazine letters, find a match, and cross it off. If you ever can't find a match, return false.

mag_letters = list(magazine)

for char in ransom_note:
    if char not in mag_letters:
        return False
    mag_letters.remove(char)   # linear scan and removal each time

return True

The remove call scans the entire list to find the first match. With a note of length n and a magazine of length m, that's O(n * m) in the worst case. If both strings are 10,000 characters long, that's 100 million operations.

Spotting the pattern

This is a Hash Map problem. The key question to ask yourself:

How do I check if I have enough of each letter without scanning the whole magazine for every letter I need?

Answering that is where it clicks, and it's exactly what the guided walkthrough below builds with you: the pattern reasoning, a progressive hint ladder that never spoils the answer, a row-by-row dry run, the optimized solution, and an in-browser editor to run your code against real test cases.