Strange Printer
Real-world version: Sign Press PassesThe statement here is our own: the same inputs, outputs and technique.
A hot-foil press finishes engraved name plates one span at a time.
A plate is a row of cells numbered from 0. In a single pass the operator picks one glyph and one contiguous span of cells, and the press drives that glyph into every cell of the span. A pass wipes out whatever those cells held before it, so each cell ends up showing the glyph of the last pass that covered it.
Every plate starts blank, so a cell that no pass ever covers stays blank and the plate is rejected.
Given target, the wording the finished plate must read, return the smallest number of passes that leaves the plate reading exactly target.
Examples
Example 1
- Input
- target = "kmk"
- Output
- 2
Press `k` over cells 0 through 2, then press `m` over cell 1 on its own. Two passes, and the plate reads `kmk`.
Example 2
- Input
- target = "wxyz"
- Output
- 4
Press `w` on cell 0, `x` on cell 1, `y` on cell 2, `z` on cell 3. Four passes, and the plate reads `wxyz`.
Example 3
- Input
- target = "ttqqt"
- Output
- 2
Press `t` over cells 0 through 4, then press `q` over cells 2 and 3. Two passes, and the plate reads `ttqqt`.
Example 4
- Input
- target = "pqpq"
- Output
- 3
Press `p` over cells 0 through 2, then `q` on cell 1, then `q` on cell 3. Three passes, and the plate reads `pqpq`.
Example 5
- Input
- target = "vvvv"
- Output
- 1
One pass of `v` over cells 0 through 3 leaves the plate reading `vvvv`.
Constraints
- 1 <= target.length <= 100
- target consists 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.
def strange_printer(target: str) -> int:public int strangePrinter(String target)Checking your plan…
How this problem was checked
- Passed: Reference solution run against 16 test cases: 16 passed
- Passed: 5 worked examples confirmed by running the code
- Passed: 0 eight-word sequences shared with the parent problem's text
- Passed: Agrees with an independent brute-force solution on random inputs
- Passed: Test set shown to catch deliberately broken solutions
- Passed: Reviewed by a separate quality pass
- Passed: Function arity matches the parent problem's