0227HardStringDynamic Programming

Mirror-Reading Ribbon Snips

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 dyeing line prints a long strip of colour marks. The strip reaches the finishing bench as ribbon, a string of lowercase letters naming the dye at each point along the strip from its left end.

Call a length of ribbon mirror-reading when its marks spell the same sequence scanned from either end. The finisher may snip straight across the strip at any point between two neighbouring marks, and every piece that remains afterwards must be mirror-reading. Return the fewest snips that leaves the strip in that state. A piece holding a single mark is mirror-reading, so some number of snips always works.

Examples

Example 1

Input: ribbon = "civicap"
Output: 2

Snipping after the fifth mark and again after the sixth leaves the pieces `civic`, `a` and `p`. Each of the three spells the same sequence from either end.

Example 2

Input: ribbon = "aabba"
Output: 1

A single snip after the first mark leaves `a` and `abba`, and both pieces read the same from either end.

Example 3

Input: ribbon = "zzzz"
Output: 0

The strip as delivered already spells the same sequence from either end, so the finisher hands it on untouched.

Constraints

1 <= ribbon.length <= 2000
ribbon holds lowercase English letters only

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 fewest_ribbon_snips(ribbon: str) -> int:

Java

public int fewestRibbonSnips(String ribbon)

The intended approach

Time O(n^2)Space O(n) for the one figure per prefix length

Keep one running figure per prefix length: the fewest snips that leaves that prefix in mirror-reading pieces, started off at the fallback of a piece per mark. Then grow a stretch outward from every single mark and from every gap between neighbouring marks, stopping as soon as the two ends disagree; while a stretch still matches, the prefix ending where the stretch ends can be reached with one snip more than the prefix ending where the stretch begins. The empty prefix is seeded at minus one snip so a strip that is mirror-reading end to end costs nothing.

Pythonentry point: fewest_ribbon_snips

def fewest_ribbon_snips(ribbon):
    n = len(ribbon)
    snips = [i - 1 for i in range(n + 1)]
    for center in range(n):
        left = right = center
        while left >= 0 and right < n and ribbon[left] == ribbon[right]:
            if snips[left] + 1 < snips[right + 1]:
                snips[right + 1] = snips[left] + 1
            left -= 1
            right += 1
        left, right = center, center + 1
        while left >= 0 and right < n and ribbon[left] == ribbon[right]:
            if snips[left] + 1 < snips[right + 1]:
                snips[right + 1] = snips[left] + 1
            left -= 1
            right += 1
    return snips[n]

The obvious version

Treat each position between marks as a node and lay an edge from i to j whenever ribbon[i:j] equals its own reversal, then breadth-first search from the left end for the fewest pieces and subtract one. O(n^3).

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_fewest_ribbon_snips(ribbon):
    from collections import deque
    n = len(ribbon)
    pieces = [None] * (n + 1)
    pieces[0] = 0
    queue = deque([0])
    while queue:
        i = queue.popleft()
        for j in range(i + 1, n + 1):
            if pieces[j] is not None:
                continue
            chunk = ribbon[i:j]
            if chunk == chunk[::-1]:
                pieces[j] = pieces[i] + 1
                queue.append(j)
    return pieces[n] - 1

How this problem was checked

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