:orphan:

Ransom Note
===========

.. highlight:: none

Problem
-------
https://leetcode.com/problems/ransom-note/

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:**

::

   Input: ransomNote = "a", magazine = "b"
   Output: false

**Example 2:**

::

   Input: ransomNote = "aa", magazine = "ab"
   Output: false

**Example 3:**

::

   Input: ransomNote = "aa", magazine = "aab"
   Output: true

 

**Constraints:**

- ``1 <= ransomNote.length, magazine.length <= 10``\ :sup:```5```
- ``ransomNote`` and ``magazine`` consist of lowercase English letters.

.. highlight:: python

Pattern
-------
Hash Table, String, Counting

Solution
--------
Track the number of times each letter appears in the magazine. Then, when the
letter appears in the ransom note, decrement the count. If the count is ever
negative, then the ransom note cannot be constructed from the magazine. A small
optimization is to initialize the counter dictionary with all letters in the
alphabet.

Code
----

.. literalinclude:: ../problems/easy/ransom-note/ransom_note__approach_1.py
    :language: python
    :lines: 12-

Test
----
>>> from ransom_note__approach_1 import canConstruct
>>> canConstruct("a", "b")
False
>>> canConstruct("aa", "ab")
False
>>> canConstruct("aa", "aab")
True

Complexity
----------
| :math:`m` is the length of ``ransomNote`` and :math:`n` is the length of ``magazine``
| Time: :math:`O(m + n)` — pass through both strings to build the counter and then check it
| Auxiliary Space: :math:`O(1)` — fixed-size counter

.. autofunction:: ransom_note__approach_1.canConstruct