Ransom Note From a Magazine
Problem
A sign maker cuts letters out of a spare banner to spell a new message. Given two lowercase strings note and banner, return True if note can be spelled using letters from banner, where each letter of banner can be used at most once. Both strings have up to 100,000 letters, so avoid searching the banner again for every letter of the note.
Examples
Input: note = "aab", banner = "baa"
Output: True
Why: the banner has two a's and one b, exactly what the note needsInput: note = "aa", banner = "ab"
Output: False
Why: the note needs two a's, the banner only has oneInput: note = "", banner = "xyz"
Output: True
Why: edge case, an empty note needs no letters at allHints
0 / 3
Order does not matter here, only how many of each letter you have. What single table would summarise the banner?
Count every letter of the banner once. Then each letter of the note is a withdrawal from that count.
Walk the note and subtract one from its letter's count. If a count would drop below zero, the banner ran out of that letter, so return False.
Solution
Only the number of copies of each letter matters, so the banner is reduced to a table of letter counts in one pass. Each letter of the note then spends one copy from that table, and the first letter whose count is already zero proves the note cannot be made. Every letter of both strings is touched once, so time is O(n + m), and the table holds at most 26 entries, so extra space is O(1).
from collections import Counter
def can_spell(note, banner):
stock = Counter(banner) # letter -> copies left
for ch in note:
if stock[ch] == 0:
return False # this letter has run out
stock[ch] -= 1
return True
print(can_spell("aab", "baa")) # -> True
print(can_spell("aa", "ab")) # -> False
print(can_spell("", "xyz")) # -> TrueStuck on the idea rather than the code? Frequency Counting covers it.