Stamping The Sequence: Reverse Greedy Simulation

You have a stamp string and a target string. You start with a string of all '?' characters the same length as the target. At each step, you can place the stamp at any position i, which overwrites the characters at positions i through i + len(stamp) - 1 with the stamp characters. The last stamp applied at any position wins. Return a sequence of stamp positions that produces the target, or an empty array if it is impossible. The answer must use at most 10 * len(target) stamps.

This is LeetCode 936: Stamping The Sequence, a hard problem that looks intimidating until you realize you should think about it backwards instead of forwards.

Why forward simulation is hard

If you try to figure out the stamping order from left to right, you immediately run into trouble. The stamp can overlap with itself. Later stamps overwrite earlier ones. The same position might need to be stamped multiple times. Figuring out the exact order that produces the target requires reasoning about which characters will be overwritten and which will survive, and that quickly becomes combinatorial.

For example, if stamp = "abc" and target = "ababc", you need to stamp at position 0, then at position 2. The second stamp overwrites position 2 (changing it from 'c' to 'a'). If you stamped in the wrong order, you would get "abcbc" instead. The order is not obvious from looking at the target alone.

The key insight: work backwards

Instead of building the target from scratch, reverse the process. Start with the target and try to "un-stamp" it back to all '?' characters. At each step, find a position where the stamp matches the current string (treating '?' as a wildcard that matches anything), then replace those characters with '?'. Repeat until the entire string is '?'.

Why does this work? If the last stamp was placed at position i, then target[i..i+m-1] must exactly equal the stamp. Replacing those positions with '?' effectively undoes that last stamp. Now the second-to-last stamp is the most recent one in the remaining string, and you can find and undo it the same way.

The wildcard rule is what makes the reverse approach powerful. Once a position has been "un-stamped" to '?', it can match any stamp character. This means that stamps which originally overlapped are no longer a problem. You erase the last stamp fully, and the overlap positions become wildcards that happily match whatever earlier stamp produced them.

Walking through the reverse approach

Let's trace through stamp = "abc", target = "ababc" step by step.

The recorded positions in reverse order are [2, 0]. Reversing gives [0, 2], which is the stamping order. You can verify: stamp at 0 produces "abc??", then stamp at 2 overwrites positions 2-4 to produce "ababc".

The solution

Here is the complete solution in Python:

def movesToStamp(stamp, target):
    s = list(stamp)
    t = list(target)
    result = []
    total_stamped = 0
    n, m = len(t), len(s)

    def can_stamp(pos):
        stamped = 0
        for i in range(m):
            if t[pos + i] == '?':
                continue
            if t[pos + i] != s[i]:
                return False
            stamped += 1
        return stamped > 0

    def do_stamp(pos):
        count = 0
        for i in range(m):
            if t[pos + i] != '?':
                t[pos + i] = '?'
                count += 1
        return count

    changed = True
    while changed:
        changed = False
        for i in range(n - m + 1):
            if can_stamp(i):
                total_stamped += do_stamp(i)
                result.append(i)
                changed = True
        if total_stamped == n:
            break

    return result[::-1] if total_stamped == n else []

Here is what each piece does:

1. can_stamp(pos) checks whether the stamp matches the current string at position pos. Characters that are already '?' are treated as wildcards and always match. At least one non-'?' character must match, otherwise this stamp would not make progress.
2. do_stamp(pos) replaces all non-'?' characters at the stamp window with '?', returning how many characters were newly erased.
3. The outer loop repeatedly scans all possible stamp positions. Each scan that finds at least one valid stamp sets changed = True and keeps going. If a full scan finds nothing new, the loop stops.
4. The result is reversed at the end because we collected positions in reverse chronological order (last stamp first).

Why the greedy approach is correct

At each step, any valid un-stamp position is safe to apply. No matter which matching position you choose first, the remaining positions will still be discoverable later. This is because erasing characters to '?' only makes future matches easier (wildcards match everything), never harder. You cannot create a situation where erasing one position blocks another.

This greedy property means you do not need backtracking or dynamic programming. A simple loop that scans for matches and erases them is sufficient.

Complexity analysis

In the worst case, each scan only erases one position's worth of characters, leading to O(n) scans. Each scan checks up to n - m + 1 positions, and each check takes O(m) time. For the problem's constraints (n up to 1000, m up to 1000), this is efficient enough.

Building blocks

This problem is built on two reusable patterns that CodeBricks drills independently.

1. Reverse simulation

Instead of simulating a process forward to figure out the construction order, reverse the process and undo it step by step. This shows up in many problems where the forward direction is ambiguous or order-dependent, but the reverse direction is greedy and unambiguous.

# General reverse simulation pattern
result = []
while not fully_undone(state):
    pos = find_any_valid_undo(state)
    if pos is None:
        return impossible
    apply_undo(state, pos)
    result.append(pos)
return result[::-1]

The key requirement for reverse simulation is that each undo step must be independent: undoing one operation should not block other valid undos. If this property holds, any order of undos produces the same final result, and greedy works.

2. Greedy matching with wildcards

The can_stamp function uses a wildcard-matching pattern where '?' matches any character. This is a simpler version of the wildcard matching that appears in problems like Regular Expression Matching and Wildcard Matching. Here, the wildcard is one-sided (only in the target, not the stamp) and positional (exact position match, no * expansion), which makes it a simple linear scan.

Edge cases

Before submitting, make sure your solution handles these:

• Stamp equals target stamp = "abc", target = "abc": one stamp at position 0. The simplest case.
• Single character stamp stamp = "a", target = "aaaa": stamp at every position. Four stamps total, positions [0, 1, 2, 3].
• Impossible target stamp = "abc", target = "abd": the character 'd' does not appear in the stamp, so it can never be produced. Return [].
• Overlapping stamps required stamp = "abc", target = "ababc": stamps at positions 0 and 2. The reverse approach handles this naturally.
• Full overlap stamp = "abca", target = "abcabca": multiple stamps where the suffix of one stamp matches the prefix of the next. The wildcard matching in reverse handles these overlaps cleanly.

From understanding to recall

You have read the reverse simulation approach and it makes sense. Scan for stamp matches, erase them to '?', repeat, reverse. But can you write the can_stamp and do_stamp functions from scratch under time pressure?

The details matter: checking that stamped > 0 so you do not make zero-progress matches, using '?' as the wildcard sentinel, and reversing the result at the end. These are easy to forget when you are nervous in an interview.

Spaced repetition closes that gap. You practice writing the reverse greedy simulation from scratch at increasing intervals. After a few rounds, the pattern is automatic. You see "construct a sequence by stamping" and immediately think "reverse it, erase matches greedily." The code flows out without hesitation.

The reverse simulation pattern is one of roughly 60 reusable building blocks that cover hundreds of LeetCode problems. Learning them individually and drilling them with spaced repetition is far more effective than grinding random problems and hoping they stick.

Related posts

• Decode String - Stack-based string construction where nested brackets define repeated segments
• String Compression - In-place string transformation with careful index tracking
• Find and Replace in String - Simultaneous string replacements at specified positions, another problem where working backwards simplifies ordering

CodeBricks breaks the stamping the sequence LeetCode problem into its reverse simulation and greedy matching building blocks, then drills them independently with spaced repetition. You type each piece from scratch until the pattern is automatic. When a reverse greedy simulation question shows up in your interview, you do not think about it. You just write it.