Skip to content
Work Practice Products Coding interviews Machine learning coding Quant developer HFT course Blog Method Why me About Book a call

Coding · Arrays and hashing

Cut a note out of a magazine

Easy · Target 10 minutes · Arrays and hashing· Type asked at

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

InputOutputWhy
note = "aa", magazine = "ab"falseThe magazine has only the one a and the note needs two of them.
note = "aa", magazine = "aab"trueThere are two copies of a to cut out and the b is just left over.
note = "moon", magazine = "monsoon"trueThe 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.
Console⌘/Ctrl + Enter runs

Write a solution and run it against the real test table.


Keep going

Preparing for a real process? Quant interview preparation, or book a free 20-minute call.