Show problems as
Classic problem #1055MediumTwo PointersStringBinary SearchGreedy

Shortest Way to Form String

Real-world version: Fewest Passes Of The Letter Stencil
Tracked in this browser only
Read Shortest Way to Form String on LeetCode(opens in a new tab)

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

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

Python
def shortest_way(stencil: str, wanted: str) -> int:
Java
public int shortestWay(String stencil, String wanted)

More on the same topics