0411HardStringDynamic Programming

Sign Press Passes

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.

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

Python

def strange_printer(target: str) -> int:

Java

public int strangePrinter(String target)

The intended approach

Time O(n^3)Space O(n^2)

Build a table over spans of the plate, filled bottom up so no recursion is needed: `dp[i][j]` is the fewest passes for `target[i..j]`. The base cost of adding cell `j` to a span is one extra pass, and whenever some cell `k` inside the span already carries `target[j]`, the pass that covers `k` can be stretched to reach `j`, which charges `dp[i][k]` plus the cost of the cells strictly between `k` and `j`. The answer sits at `dp[0][n-1]`.

Pythonentry point: strange_printer

def strange_printer(target):
    # Time O(n^3): the two span bounds give O(n^2) table cells and each cell
    # scans every interior split. Space O(n^2) for the full span table.
    n = len(target)
    if n == 0:
        return 0
    dp = [[0] * n for _ in range(n)]
    for i in range(n - 1, -1, -1):
        dp[i][i] = 1
        for j in range(i + 1, n):
            best = dp[i][j - 1] + 1
            for k in range(i, j):
                if target[k] == target[j]:
                    inner = dp[k + 1][j - 1] if k + 1 <= j - 1 else 0
                    cand = dp[i][k] + inner
                    if cand < best:
                        best = cand
            dp[i][j] = best
    return dp[0][n - 1]

The obvious version

Breadth-first search that undoes passes. A state marks which cells still have to match `target`; peeling the final pass means clearing a contiguous span whose still-required cells all carry one glyph. The first time every cell is cleared gives the pass count.

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_press_passes(target):
    from collections import deque
    n = len(target)
    if n == 0:
        return 0
    start = tuple(target)
    goal = tuple([None] * n)
    seen = {start}
    frontier = deque([(start, 0)])
    while frontier:
        state, used = frontier.popleft()
        if state == goal:
            return used
        for i in range(n):
            glyph = None
            for j in range(i, n):
                here = state[j]
                if here is not None:
                    if glyph is None:
                        glyph = here
                    elif here != glyph:
                        break
                if glyph is None:
                    continue
                nxt = list(state)
                for p in range(i, j + 1):
                    nxt[p] = None
                nxt = tuple(nxt)
                if nxt not in seen:
                    seen.add(nxt)
                    frontier.append((nxt, used + 1))
    return -1

How this problem was checked

Reference solution executed against 16 test cases — 16 passed
5 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