Stamping the Sequence [Hard] — Reverse Greedy

Problem Statement

You have a stamp of length m and a target string of length n. Starting with ???...? (n question marks), you can stamp anywhere. Return a sequence of stamp positions to convert ??? to target. (10nm steps max.)

Input: stamp="abc", target="ababc" → Output: [0,2] (one valid answer)

Intuition

Work backwards: try to "unstamp" by finding a window in target that matches the stamp (with some wildcards * already erased). Replace with *. Repeat until all *. Output positions in reverse.

Solutions

Python

def movesToStamp(stamp: str, target: str) -> list[int]:
    m, n = len(stamp), len(target)
    target = list(target)
    res = []
    total_replaced = 0

    def try_stamp(pos):
        nonlocal total_replaced
        replaced = 0
        for i, c in enumerate(stamp):
            if target[pos+i] == '*':
                continue
            if target[pos+i] != c:
                return 0
            replaced += 1
        for i in range(m):
            if target[pos+i] != '*':
                target[pos+i] = '*'
        return replaced

    while total_replaced < n:
        made_progress = False
        for pos in range(n - m + 1):
            r = try_stamp(pos)
            if r > 0:
                total_replaced += r
                res.append(pos)
                made_progress = True
        if not made_progress:
            return []

    return res[::-1]

Complexity

Time: O(n×m×(n-m)) in the worst case
Space: O(n)