1135HardArrayHash TableStringDynamic ProgrammingBacktrackingBit ManipulationMemoizationBitmask

Cutting Letters Out of Stencils

Tracked in this browser only

Trains the technique from

This is an original problem, written from a brief that listed the technique, the difficulty, the topics, the function shape and the input bounds — none of that problem's wording, examples, hints or editorials. The link is there so you can map your practice onto the standard set.

Same function shape, different story and different numbers.

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 is preloaded with this. It matches the parent problem's shape, so a solution that works here transfers to a judge unchanged.

Python

def min_stickers(stencils: list[str], target: str) -> int:

Java

public int minStickers(String[] stencils, String target)

The intended approach

Time O(2^t * s * t) for a target of t letters and s stencils.Space O(2^t) for the patterns.

The target is at most fifteen letters long, so which of its positions are already spelt fits in a bit pattern, and the fewest stencils for each pattern can be built up from the empty one. Positions rather than letters are tracked because the target may hold a letter several times over. From a pattern, look at the lowest position not yet spelt. Whatever stencils are used in the end, one of them must supply that position, so only stencils holding that letter are worth trying, and forcing that position cuts out an enormous amount of pointless work. For each such stencil, spend its letters on as many unspelt positions as they will cover, working forwards and decreasing a running tally per letter so no letter is spent more often than the stencil holds it. Covering as many positions as possible is never a mistake, because a pattern covering more positions leaves less to do and so never needs more stencils. Positions carrying the same letter are interchangeable, so it does not matter which of them a short supply covers. The answer is the entry for the pattern with everything spelt, and a pattern never reached means the target cannot be spelt.

Pythonentry point: min_stickers

def min_stickers(stencils, target):
    n = len(target)
    full = (1 << n) - 1
    big = 1 << 30
    best = [big] * (1 << n)
    best[0] = 0
    tallies = []
    for word in stencils:
        tally = {}
        for ch in word:
            tally[ch] = tally.get(ch, 0) + 1
        tallies.append(tally)
    for mask in range(1 << n):
        if best[mask] >= big:
            continue
        spot = 0
        while spot < n and (mask >> spot) & 1:
            spot += 1
        if spot == n:
            continue
        for tally in tallies:
            if target[spot] not in tally:
                continue
            left = dict(tally)
            grown = mask
            for i in range(spot, n):
                if (grown >> i) & 1:
                    continue
                ch = target[i]
                if left.get(ch, 0) > 0:
                    left[ch] -= 1
                    grown |= 1 << i
            if best[mask] + 1 < best[grown]:
                best[grown] = best[mask] + 1
    return best[full] if best[full] < big else -1

The obvious version

Work with what is left to spell rather than with patterns. Hold the leftover letters as a sorted word, starting from the whole target, and walk outwards a stencil at a time: for each stencil, strike its letters off the leftovers one by one and see what word remains. The first time nothing is left, the number of stencils spent is the fewest. Stencils that strike nothing off are skipped so the walk cannot circle.

This is not filler. It was written independently of the fast solution and the two were run against thousands of random inputs to confirm they agree — which is how the answer above is known to be right. Read it when the intended approach feels like a rabbit pulled out of a hat.

Python

def bf_min_stickers(stencils, target):
    from collections import deque
    start = "".join(sorted(target))
    seen = {start: 0}
    queue = deque([start])
    while queue:
        need = queue.popleft()
        used = seen[need]
        if need == "":
            return used
        for word in stencils:
            pool = list(word)
            leftover = []
            for ch in need:
                if ch in pool:
                    pool.remove(ch)
                else:
                    leftover.append(ch)
            rest = "".join(leftover)
            if rest == need:
                continue
            if rest not in seen:
                seen[rest] = used + 1
                queue.append(rest)
    return -1

How this problem was checked

Reference solution executed against 15 test cases — 15 passed
3 worked examples confirmed by running the code
0 eight-word sequences shared with the parent problem's text
Agrees with an independent brute-force implementation on random inputs
Test set proven to catch deliberately broken solutions
Reviewed by a separate quality pass
Function arity matches the parent problem's

Create a free account to unlock the solution

See the step-by-step animation, the intuition, and clean code in every language — free, no credit card.

Create a free account Already have an account? Sign in