Stickers to Spell Word

HardDynamic Programmingbitmask dp

Solve this the way you would in the interview: out loud, on a timer, with an AI interviewer asking follow-ups while you code. You get a scored report at the end.

Practice this as a mock interviewFree to start, no account needed

Problem

You have unlimited copies of each sticker in stickers; each sticker is a lowercase word. You may cut individual letters out of stickers and rearrange them freely. Return the minimum total number of stickers needed to collect enough letters to spell target (every letter of target, with multiplicity). Leftover letters are fine. If target cannot be spelled at all, return -1.

Examples

Input: stickers = ["with","example","science"], target = "thehat"
Output: 3
Two "with" stickers and one "example" provide t, h, e, h, a, t.
Input: stickers = ["notice","possible"], target = "basicbasic"
Output: -1
No sticker has the letter "a".

Constraints

  • 1 <= stickers.length <= 50
  • 1 <= stickers[i].length <= 10
  • 1 <= target.length <= 15
  • `stickers[i]` and `target` consist of lowercase English letters

What the interviewer grades

A correct solution is one of five scores. The report also grades problem understanding (did you clarify inputs and edge cases before coding), problem solving, communication while you work, code quality, and testing. See a sample report, or read up on the pattern in the lessons.

More bitmask dp problems