Ransom Note

Magazine Photo by Rhema Kallianpur

This post is part of the Algorithms Problem Solving series.

Problem description

This is the Ransom Note problem. The description looks like this:

Given an arbitrary ransom note string and another string containing letters from all the magazines, write a function that will return true if the ransom note can be constructed from the magazines; otherwise, it will return false.

Each letter in the magazine string can only be used once in your ransom note.


# ransomNote = "a", magazine = "b"
# => false

# ransomNote = "aa", magazine = "ab"
# => false

# ransomNote = "aa", magazine = "aab"
# => true


def can_construct(ransom_note, magazine):
    if ransom_note == '':
        return True

    if magazine == '':
        return False

    letters_counter = {}

    for letter in magazine:
        if letter in letters_counter:
            letters_counter[letter] += 1
            letters_counter[letter] = 1

    for char in ransom_note:
        if char not in letters_counter or letters_counter[char] == 0:
            return False

        letters_counter[char] -= 1

    return True


Patreon Become a Patron Coffee icon Buy me a coffee