Clip Letters Into a Note

EasyArrays & Hashing

Problem

For a scrapbook, you want to spell out note using letters cut from an old newspaper. Every letter in the newspaper text paper can be cut out and used at most once.

Return true if note can be built from the letters of paper, and false otherwise.

Example 1

Input:
note = "cab", paper = "abacus"
Output:
true

paper has a 'c', an 'a' and a 'b' to spare.

Example 2

Input:
note = "book", paper = "kobe"
Output:
false

note needs two 'o's but paper has only one.

Constraints

  • 0 ≤ note.length, paper.length ≤ 10^5
  • Both strings contain only lowercase English letters.

Hint

Show the first hint

Only how many of each letter you have matters, not where they are.

Walkthrough

How to approach it

01Clarify before coding

  • Can a newspaper letter be reused? No, each one is used at most once.
  • Is an empty note always possible? Yes.
  • Only lowercase letters? Yes, so 26 counters are enough.

02Brute force

For each letter of the note, search paper for an unused copy and mark it used.

Cost: O(|note| · |paper|) time: up to 10^10 steps.

The rest of the walkthrough is in the app

The full walkthrough (key insight, step-by-step, dry run, complexity, edge cases, pitfalls, follow-ups) and solutions in Python and JavaScript are in the app, next to an editor and a terminal that runs your code against the tests.

Solve it in the browserStart free

This problem is part of Pro.