LeetCode 936: Stamping The Sequence

Problem Restatement

We are given two strings:

stamp
target

Initially, we start with a string made entirely of question marks:

"?????"

with the same length as target.

In one move, we may place the stamp string over any position and overwrite the characters.

For example:

stamp  = "abc"
before = "?????"
after  = "??abc"

The goal is to build target.

We must return a sequence of stamping positions that creates target.

If multiple answers exist, any valid answer is accepted.

If impossible, return:

[]

The answer length must not exceed:

10 * len(target)

The official statement defines stamping onto question marks and asks for a valid sequence of moves producing target. (leetcode.com)

Input and Output

Function shape:

class Solution:
    def movesToStamp(self, stamp: str, target: str) -> list[int]:
        ...

Examples

Example 1:

stamp = "abc"
target = "ababc"

One valid process is:

Start:

?????

Stamp at position 0:

abc??

Stamp at position 2:

ababc

So one valid answer is:

[0, 2]

Example 2:

stamp = "abca"
target = "aabcaca"

One valid answer is:

[3, 0, 1]

These are the standard examples from the official problem. (github.com)

First Thought: Build the Target Forward

One idea is to simulate the construction directly.

Start from:

?????

and repeatedly stamp valid positions until the target appears.

But this is difficult.

A stamp can overwrite earlier characters, and many different move orders are possible.

It is hard to know which stamp should be applied first.

Key Insight

Reverse the process.

Instead of constructing target from question marks, remove the stamp from target.

Suppose a window already matches the stamp.

For example:

stamp  = "abc"
target = "ababc"

The substring:

"abc"

can be erased into:

"???"

This reverse direction is easier because once characters become '?', they are flexible and help future removals.

We repeatedly find stampable windows and erase them.

The reverse removal order is the reverse of the final answer.

Graph Interpretation

For every window of length:

m = len(stamp)

inside target, track:

If todo becomes empty, the window can be stamped immediately.

When a character becomes '?', it may help neighboring windows reduce their todo sets.

This behaves like BFS dependency removal.

Algorithm

Let:

m = len(stamp)
n = len(target)

For every window start i:

1. Compare target[i:i+m] with stamp.
2. Store:
   • matching positions
   • mismatching positions

If a window has no mismatches, it can already be removed.

Push its index into a queue.

Then process the queue.

When removing a window:

1. For every newly erased position:
   • mark it visited
   • update all overlapping windows
2. If another window now has no mismatches:
   • push it into the queue

Store the removal order.

At the end:

• if every character was erased, reverse the order and return it
• otherwise return []

Walkthrough

Use:

stamp = "abc"
target = "ababc"

Window size:

3

Possible windows:

Window 2 can be erased immediately.

Erase:

ab???

Now positions 2, 3, 4 are flexible.

This helps window 0.

Window 0 becomes removable.

Erase:

?????

Removal order:

[2, 0]

Reverse it:

[0, 2]

This is a valid stamping order.

Correctness

A window can be erased exactly when every non-erased character inside it matches the corresponding character in stamp. Replacing that window with question marks is therefore a valid reverse stamping operation.

The algorithm maintains, for every window, the set of positions still preventing removal. A window enters the queue only when all of those blocking positions disappear, meaning the window has become fully removable.

Whenever a position is erased, every overlapping window is updated. If that erased position was previously blocking a window, it is removed from that window’s remaining mismatch set. Therefore, the algorithm eventually discovers every window that becomes removable due to earlier erasures.

Each processed window corresponds to one valid reverse stamping operation. The algorithm records these reverse operations in order.

If the algorithm erases every character, then reversing the recorded operations produces a valid forward stamping sequence. Applying those stamps reconstructs the original target because each reverse removal corresponded to a valid forward stamp placement.

If some character cannot be erased, then no valid reverse sequence exists. Since every valid forward stamping process corresponds to a valid reverse erasure process, constructing the target is impossible, and returning [] is correct.

Complexity

Let:

m = len(stamp)
n = len(target)

Implementation

from collections import deque

class Solution:
    def movesToStamp(self, stamp: str, target: str) -> list[int]:
        m = len(stamp)
        n = len(target)

        queue = deque()
        done = [False] * n
        ans = []

        windows = []

        for i in range(n - m + 1):
            made = set()
            todo = set()

            for j in range(m):
                if target[i + j] == stamp[j]:
                    made.add(i + j)
                else:
                    todo.add(i + j)

            windows.append((made, todo))

            if not todo:
                ans.append(i)

                for j in range(i, i + m):
                    if not done[j]:
                        done[j] = True
                        queue.append(j)

        while queue:
            i = queue.popleft()

            start = max(0, i - m + 1)
            end = min(n - m, i)

            for j in range(start, end + 1):
                made, todo = windows[j]

                if i in todo:
                    todo.remove(i)

                    if not todo:
                        ans.append(j)

                        for pos in made:
                            if not done[pos]:
                                done[pos] = True
                                queue.append(pos)

        if all(done):
            return ans[::-1]

        return []

Code Explanation

done[pos] tracks whether a character position has already been erased:

done = [False] * n

For every window, we store:

(made, todo)

made contains positions already matching the stamp.

todo contains positions still blocking removal.

If todo is empty:

if not todo:

the window can immediately be erased.

We then mark all positions in that window as erased:

done[j] = True
queue.append(j)

The queue stores newly erased positions.

For each erased position i, we update all overlapping windows:

start = max(0, i - m + 1)
end = min(n - m, i)

If position i was blocking a window:

if i in todo:
    todo.remove(i)

and the window now has no blockers:

if not todo:

then it becomes removable.

Finally:

return ans[::-1]

because we recorded reverse removals, but the required answer is the forward stamping order.

Testing

def apply_stamps(stamp, n, moves):
    arr = ["?"] * n
    m = len(stamp)

    for pos in moves:
        for i in range(m):
            arr[pos + i] = stamp[i]

    return "".join(arr)

def run_tests():
    s = Solution()

    moves = s.movesToStamp("abc", "ababc")
    assert apply_stamps("abc", 5, moves) == "ababc"

    moves = s.movesToStamp("abca", "aabcaca")
    assert apply_stamps("abca", 7, moves) == "aabcaca"

    assert s.movesToStamp("abc", "def") == []

    moves = s.movesToStamp("a", "aaaa")
    assert apply_stamps("a", 4, moves) == "aaaa"

    print("all tests passed")

run_tests()