easy

Ransom Note

Check whether one string can be built from the letters of another by counting the available letters in a hash map and spending them.

1. Define the problem

Ransom Note

Given two strings ransomNote and magazine, return true if ransomNote can be built using the letters of magazine, and false otherwise. Each letter in magazine may be used at most once. Count every letter in magazine in a hash map from letter to how many copies you own. Then read the note letter by letter and spend one copy each time. If a letter you need has no copies left, the note cannot be built.

Constraints

  • 1 ≤ ransomNote.length, magazine.length ≤ 105
  • Both strings consist of lowercase English letters

Example

InputransomNote = "aab", magazine = "aabbc"
Outputtrue

Explanation The magazine holds two a, two b and one c. The note needs two a and one b, all of which are available.

2. Know the words first

In plain terms

Hash map
A lookup table of key and value pairs. Here the key is a letter and the value is how many copies of that letter are still available.
Frequency count
A tally of how many times each item appears. Building one is usually the first move in a letter or word counting question.
3. Visualize the solution

One cell per letter key, value = copies still available

One cell per letter key, value = copies still available
Statusinit

Nothing has been counted yet, so every letter shows a dash.

What happens in this step

ransomNote = "aab"
magazine = "aabbc"

available = empty
The three cells are the letters the magazine will turn out to hold.
Step 1 of 6

Steps to visualize

  1. Each cell is one letter key in the hash map. Its value is how many copies remain.
  2. First read the magazine and count every letter it contains.
  3. Then read the note one letter at a time and take one copy away.
  4. A letter with zero copies left means the note needs more than the magazine has.
  5. Finishing the note without running out means the answer is true.
4. Walk through the code

Walk through the code

Same walkthrough, now with the code. Press Next to move one step and watch which lines run.

One cell per letter key, value = copies still available
Statusinit

Nothing has been counted yet, so every letter shows a dash.

What happens in this step

ransomNote = "aab"
magazine = "aabbc"

available = empty
The three cells are the letters the magazine will turn out to hold.
Step 1 of 6
5. Solution

Solution

solution.tsTypeScript
function canConstruct(ransomNote, magazine) {
  const available = new Map();

  for (const char of magazine) {
    available.set(char, (available.get(char) || 0) + 1);
  }

  for (const char of ransomNote) {
    const left = available.get(char) || 0;

    if (left === 0) {
      return false;
    }

    available.set(char, left - 1);
  }

  return true;
}
Time
O(n + m)
Space
O(1) because at most 26 letter keys are stored
6. Test cases

Test cases

InputExpectedCovers
ransomNote = "aab", magazine = "aabbc"trueexample from the description
ransomNote = "a", magazine = "b"falsethe needed letter is not in the magazine at all
ransomNote = "aa", magazine = "ab"falsethe letter exists but there are too few copies
ransomNote = "abc", magazine = "cba"trueevery letter is used exactly once
ransomNote = "aaaa", magazine = "aaa"falsethe note asks for more letters than exist
ransomNote = "meeting", magazine = "timeengagement"truelonger words where the letters are spread out

Keep reading