Show problems as
Classic problem #691HardArrayHash TableStringDynamic ProgrammingBacktrackingBit ManipulationMemoizationBitmask

Stickers to Spell Word

Real-world version: Cutting Letters Out of Stencils
Tracked in this browser only
Read Stickers to Spell Word on LeetCode(opens in a new tab)

The statement here is our own: the same inputs, outputs and technique.

There is an unlimited supply of every stencil in stencils, and each stencil is a word of lowercase letters. Letters may be cut out of a stencil and arranged in any order.

Spell the word target from cut-out letters, using as few stencils as possible. Letters that are not needed are simply left over.

Return the fewest stencils needed, or -1 when the target cannot be spelt at all.

Examples

Example 1

Input
stencils = ["a"], target = "aa"
Output
2

One stencil supplies a single a, so two of them are needed to spell two.

Example 2

Input
stencils = ["abc", "bcd"], target = "abcd"
Output
2

Neither stencil holds all four letters, but one supplies the a and the other supplies the d, and between them the middle two are covered as well.

Example 3

Input
stencils = ["a"], target = "b"
Output
-1

The only stencil holds no b at all, so the target can never be spelt.

Constraints

  • 1 <= stencils.length <= 50
  • 1 <= stencils[i].length <= 10
  • 1 <= target.length <= 15
  • stencils[i] and target hold only lowercase English letters

The signature

The editor starts with this. It matches the parent problem's shape, so a solution that works here works on a standard judge unchanged.

Python
def min_stickers(stencils: list[str], target: str) -> int:
Java
public int minStickers(String[] stencils, String target)

More on the same topics