Cut a note out of a magazine
You're given two lowercase strings, note and magazine. I'd like you to say
whether the note can be put together from letters cut out of the magazine, where each letter in the magazine can
only be used once. Either string may be empty.
Examples
| Input | Output | Why |
|---|---|---|
note = "aa", magazine = "ab" | false | The magazine has only the one a and the note needs two of them. |
note = "aa", magazine = "aab" | true | There are two copies of a to cut out and the b is just left over. |
note = "moon", magazine = "monsoon" | true | The magazine has an m, three copies of o and two copies of n, which is more than enough. |
Constraints
- 0 ≤ note.length, magazine.length ≤ 10⁵
- both strings hold lowercase English letters only
Hints
Hint 1
The order of the letters in either string doesn't matter at all here, so ask yourself what's left of each string once you throw the order away.
Hint 2
What's left is how many copies of each letter there are, and with only 26 lowercase letters you can keep those counts in an array of 26 numbers.
Hint 3
Fill the counts from the magazine and then take one off for every letter of the note, and you can stop and say no the moment one of them would drop below zero.
Where people lose marks
- Checking only that every letter of the note appears somewhere in the magazine. That says yes to aa against ab, and the whole point of the problem is that each copy can be used once.
- Counting the note and the magazine into two tables and then comparing them with equality. The magazine is allowed to have letters left over, so what you want is that each count in the note is at most the count in the magazine.
- Sorting both strings and walking along them. It works and it's a fair first answer, but it costs O(n log n) and the interviewer will usually ask you for the counting version next.
Dry run on "noon","moon"
Read it one frame at a time, the way you would trace the code on paper in an interview. Each frame shows the state after the step it describes.
-
Step 1 / 5letterm0n1o2count101122note"noon"
One pass over "moon" fills the counts, so that's what the magazine has to give before we spend any of it on the note.
-
Step 2 / 5letterm0n1o2count100122i0
We cut out a n for position 0 of the note, which takes the count for n down to 0.
-
Step 3 / 5letterm0n1o2count100112i1
We cut out a o for position 1 of the note, which takes the count for o down to 1.
-
Step 4 / 5letterm0n1o2count100102i2
We cut out a o for position 2 of the note, which takes the count for o down to 0.
-
Step 5 / 5letterm0n1o2count100102i3answerfalse
The note needs another n but its count is already at zero, so the magazine has run out of n and the answer is false.
How to think about it
You'll usually hear this one called the Ransom Note problem and it's the simplest place I know to practise the counting table. Since the order of the letters doesn't matter all you need from the magazine is how many copies of each letter it has, and with lowercase letters only that's an array of 26 counts.
So you make one pass over the magazine adding one to the count of every letter you see. Then you make a pass over the note taking one away for each of its letters, and if a count is already at zero when you come to take from it then the magazine has run out of that letter and you can say no straight away. If you get to the end of the note without that happening then every letter it needed was there.
That's O(m + n) time for strings of lengths m and n and only 26 counts of extra memory. If the note is longer than the magazine you can say no before you count anything, which is a cheap check that's worth having in an interview even though it doesn't change the bound.
Complexity. Time O(m + n) · Space O(1), 26 counts
The solution, in six languages
Each one is compiled and run against the test table before it is published. Java is reviewed by hand.
def can_build_note(note, magazine):
if len(note) > len(magazine):
return False
count = [0] * 26
for ch in magazine:
count[ord(ch) - 97] += 1
for ch in note:
k = ord(ch) - 97
if count[k] == 0:
return False # the magazine has run out of this letter
count[k] -= 1
return True#include <string>
using namespace std;
bool solve(const string& note, const string& magazine) {
if (note.size() > magazine.size()) return false;
int count[26] = {0};
for (char ch : magazine) count[ch - 'a']++;
for (char ch : note) {
if (count[ch - 'a'] == 0) return false; // the magazine has run out of this letter
count[ch - 'a']--;
}
return true;
}class Solution {
public boolean canBuildNote(String note, String magazine) {
if (note.length() > magazine.length()) return false;
int[] count = new int[26];
for (char ch : magazine.toCharArray()) count[ch - 'a']++;
for (char ch : note.toCharArray()) {
if (count[ch - 'a'] == 0) return false; // the magazine has run out of this letter
count[ch - 'a']--;
}
return true;
}
}function canBuildNote(note, magazine) {
if (note.length > magazine.length) return false;
const count = new Array(26).fill(0);
for (const ch of magazine) count[ch.charCodeAt(0) - 97]++;
for (const ch of note) {
const k = ch.charCodeAt(0) - 97;
if (count[k] === 0) return false; // the magazine has run out of this letter
count[k]--;
}
return true;
}fn solve(note: &str, magazine: &str) -> bool {
if note.len() > magazine.len() {
return false;
}
let mut count = [0i32; 26];
for b in magazine.bytes() {
count[(b - b'a') as usize] += 1;
}
for b in note.bytes() {
let k = (b - b'a') as usize;
if count[k] == 0 {
return false; // the magazine has run out of this letter
}
count[k] -= 1;
}
true
}import qualified Data.Map.Strict as M
-- Count the magazine, then check that the note never needs more of a letter than the magazine has.
solve :: String -> String -> Bool
solve note magazine = and [M.findWithDefault 0 c have >= n | (c, n) <- M.toList need]
where
tally s = M.fromListWith (+) [(c, 1 :: Int) | c <- s]
have = tally magazine
need = tally note
Variants to try
- The strings can hold any Unicode characters. (Swap the 26-slot array for a hash map from character to count.)
- Say how many complete copies of the note the magazine could make. (Divide each letter's count in the magazine by its count in the note and take the smallest result.)
Next problems
Are two words anagrams?
Two words are anagrams when every letter occurs equally often in both. One table of counts, added for one word and taken away for the other.
Open the problem → Medium15 minThe k most frequent values
A hash map does the counting in one pass. The interesting part is ordering what you counted, and saying precisely how ties break.
Open the problem → Medium20 minGroup the words that are anagrams
Two words are anagrams when they have the same letter counts, so the whole trick is to turn each word into a key that depends on nothing else and then let a hash map do the grouping for you.
Open the problem →Write a solution and run it against the real test table.
Keep going
Are two words anagrams?
Two words are anagrams when every letter occurs equally often in both. One table of counts, added for one word and taken away for the other.
Open the problem → Medium15 minThe k most frequent values
A hash map does the counting in one pass. The interesting part is ordering what you counted, and saying precisely how ties break.
Open the problem → Medium20 minGroup the words that are anagrams
Two words are anagrams when they have the same letter counts, so the whole trick is to turn each word into a key that depends on nothing else and then let a hash map do the grouping for you.
Open the problem → Arrays and hashingThe pattern behind it
Trade memory for time: a hash map answers "have I seen this?" in O(1), and most array problems reduce to asking it the right question.
Read the pattern →Preparing for a real process? Quant interview preparation, or book a free 20-minute call.