0643MediumTwo PointersStringBinary SearchGreedy

Fewest Passes Of The Letter Stencil

Tracked in this browser only

Trains the technique from

LeetCode 1055Shortest Way to Form String

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.

A printing stencil carries the lowercase letters of stencil in a fixed left-to-right order.

One pass of the stencil prints a chosen set of its letters onto the right-hand end of the sheet. Within a pass the chosen letters come out in stencil order, each position on the stencil may be used at most once, and at least one letter must be printed; letters may be left out freely, so a pass can print anything from a single letter up to the whole stencil.

The finished sheet has to read exactly wanted. Return the smallest number of passes that produces it, or -1 when no number of passes can. The value -1 is never a valid pass count, so it is unambiguous as an answer.

Examples

Example 1

Input: stencil = "mnp", wanted = "mnpnm"
Output: 3

Print mnp on the first pass, then n on the second, then m on the third. The sheet reads mnpnm, so 3 passes are used.

Example 2

Input: stencil = "mnp", wanted = "mnq"
Output: -1

The stencil carries m, n and p only, and the sheet has to show a q, which no pass can print, so the answer is -1.

Example 3

Input: stencil = "ab", wanted = "aabb"
Output: 3

Print a on the first pass, then ab on the second, then b on the third. The sheet reads aabb, so 3 passes are used.

Constraints

1 <= stencil.length <= 1000
1 <= wanted.length <= 1000
stencil and wanted consist of 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 shortest_way(stencil: str, wanted: str) -> int:

Java

public int shortestWay(String stencil, String wanted)

The intended approach

Time O(26 * m + n) — the table costs twenty-six entries per stencil position, then one lookup per letter of wanted.Space O(26 * m) for the table.

Precompute, for every stencil position and every letter, the earliest position from there onwards carrying that letter. If some letter of wanted never appears on the stencil the sheet cannot be produced and the answer is -1. Otherwise sweep wanted keeping a cursor into the stencil: each letter is served from the earliest position at or after the cursor, and the cursor moves just past it. When the lookup reports nothing left, the current pass has been used up, so the pass count rises and the letter is served from the front of the stencil instead. Serving a letter as early as possible leaves the most stencil available for what follows, so no pass is opened before it has to be.

Pythonentry point: shortest_way

def shortest_way(stencil, wanted):
    # O(26 * m + n) time, O(26 * m) space, m the stencil length. Build a table
    # where nxt[i][c] is the earliest position from i onwards carrying letter c,
    # or -1 when the stencil has none left. A letter absent from the stencil makes
    # the sheet impossible. Otherwise read wanted once, always taking a letter
    # from the earliest position still ahead in the current pass, and open a new
    # pass only when the current one has no such position left.
    m = len(stencil)
    nxt = [[-1] * 26 for _ in range(m + 1)]
    for i in range(m - 1, -1, -1):
        row = nxt[i]
        prev = nxt[i + 1]
        for c in range(26):
            row[c] = prev[c]
        row[ord(stencil[i]) - 97] = i
    for ch in wanted:
        if nxt[0][ord(ch) - 97] == -1:
            return -1
    passes = 1
    i = 0
    for ch in wanted:
        c = ord(ch) - 97
        j = nxt[i][c]
        if j == -1:
            passes += 1
            j = nxt[0][c]
        i = j + 1
    return passes

The obvious version

Reject the sheet outright when wanted needs a letter the stencil lacks. Otherwise treat prefixes of wanted as nodes and run a shortest-path table over them: from a prefix of length i, scan the stencil once matching letters of wanted forwards to see how far a single pass starting there can reach, and record one extra pass for every prefix length up to that reach. The entry for the whole of wanted is the answer.

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_shortest_way(stencil, wanted):
    n = len(wanted)
    have = set(stencil)
    for ch in wanted:
        if ch not in have:
            return -1
    big = n + 5
    dp = [big] * (n + 1)
    dp[0] = 0
    for i in range(n):
        if dp[i] >= big:
            continue
        reach = i
        for ch in stencil:
            if reach < n and wanted[reach] == ch:
                reach += 1
        for e in range(i + 1, reach + 1):
            if dp[i] + 1 < dp[e]:
                dp[e] = dp[i] + 1
    return dp[n]

How this problem was checked

Reference solution executed against 12 test cases — 12 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