Ransom Note

Easy#383counting

You get a note and a magazine. Find out whether the note can be put together from letters cut out of the magazine, if each letter of the magazine can be used only once. Our example: the note "hello" and the magazine "shelfloor" — yes, and s, f, r and one o are left over.

383 Ransom NoteWalkthrough · 1×

Example: the note "hello", the magazine "shelfloor". Under them is the map: letter and how many of it the magazine still has.

magazinenoteshelfloorhellocount—
not reached yetcurrent lettercounted, still leftused upnot enoughthe note is made

Start with an empty map: every letter counts 0

01/35
restart · back · play · step
Speed
1function canConstruct(note, magazine):
2 count = empty map // missing keys: 0
3 for each c in magazine:
4 count[c] = count[c] + 1
5 for each c in note:
6 count[c] = count[c] - 1
7 if count[c] < 0:
8 return false
9 return true
state
count
{}
c
–
historyclick a step to go back

← → step · space play/pause

Why it works

  1. Every letter of the magazine can be used once, and where it stands does not matter. So all we need is how many of each letter the magazine has: count them first.
  2. The note spends letters: one off the count for each of its letters. A count below 0 means the note wants a letter the magazine has run out of: false at once.
  3. If the whole note is spent and nothing went below 0, every letter was there: true. Letters left in the magazine do not matter.

Complexity

Time O(m + n): one pass over the magazine and one over the note. Memory O(1): at most 26 counts for lowercase letters.

nextNow solve it yourself, no hints.

Solve on LeetCode ↗

The problem and its statement belong to LeetCode. Here are our own retelling, example and solution. Patterns Hero is not affiliated with LeetCode.