0677HardStringDynamic Programming

Fewest Tiles to Mirror the Strip

Tracked in this browser only

Trains the technique from

LeetCode 1312Minimum Insertion Steps to Make a String Palindrome

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 mosaic strip is written as strip, one lowercase letter per tile, read left to right. Each letter names a tile colour.

In one step you may buy a tile of any colour and slide it into the strip at any position: in front of the first tile, between two neighbouring tiles, or after the last tile. Tiles already on the strip are never removed and never change their order.

A strip is mirrored when the colours read from left to right are the same as the colours read from right to left.

Return the fewest steps needed to leave the strip mirrored.

Examples

Example 1

Input: strip = "cobalt"
Output: 5

Buying five tiles gives `tlabocobalt`, which reads the same in both directions and keeps the six original tiles in their original order.

Example 2

Input: strip = "aaab"
Output: 1

One bought tile is enough: sliding a `b` in front gives `baaab`, which reads the same both ways.

Example 3

Input: strip = "ggrgg"
Output: 0

This strip already reads the same in both directions, so no tile is bought.

Constraints

1 <= strip.length <= 500
strip 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 fewest_inserts(strip: str) -> int:

Java

public int fewestInserts(String strip)

The intended approach

Time O(n^2): the table has n rows and n columns, each cell filled in constant time.Space O(n): two rows of the table are held at a time.

Every tile bought is the mirror partner of a tile already on the strip, so the tiles that need no partner are exactly the ones that already sit symmetrically, and those form the longest run of tiles common to the strip and to the strip read backwards. Fill the usual table of longest common runs between the strip and its reverse, keeping only the previous row, and subtract the result from the number of tiles.

Pythonentry point: fewest_inserts

def fewest_inserts(strip):
    # tiles that need no partner are the ones shared with the strip read backwards
    n = len(strip)
    back = strip[::-1]
    prev = [0] * (n + 1)
    for i in range(1, n + 1):
        cur = [0] * (n + 1)
        here = strip[i - 1]
        for j in range(1, n + 1):
            if here == back[j - 1]:
                cur[j] = prev[j - 1] + 1
            elif cur[j - 1] >= prev[j]:
                cur[j] = cur[j - 1]
            else:
                cur[j] = prev[j]
        prev = cur
    return n - prev[n]

The obvious version

Work out the cost of every stretch of the strip, shortest stretch first. If the two end tiles of a stretch match they can be left as a mirror pair, so the cost is that of the stretch inside them; otherwise one of the two ends must be given a partner, so the cost is one plus the cheaper of dropping the left end or dropping the right end. The answer is the cost of the whole strip.

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_inserts(strip):
    n = len(strip)
    if n < 2:
        return 0
    cost = [[0] * n for _ in range(n)]
    for span in range(2, n + 1):
        for i in range(0, n - span + 1):
            j = i + span - 1
            if strip[i] == strip[j]:
                cost[i][j] = cost[i + 1][j - 1] if span > 2 else 0
            else:
                left = cost[i + 1][j]
                right = cost[i][j - 1]
                cost[i][j] = 1 + (left if left < right else right)
    return cost[0][n - 1]

How this problem was checked

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