# LeetCode 936: Stamping The Sequence

## Problem Restatement

We are given two strings:

```python
stamp
target
```

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

```text
"?????"
```

with the same length as `target`.

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

For example:

```text
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:

```python
[]
```

The answer length must not exceed:

```python
10 * len(target)
```

The official statement defines stamping onto question marks and asks for a valid sequence of moves producing `target`. ([leetcode.com](https://leetcode.com/problems/stamping-the-sequence/?utm_source=chatgpt.com))

## Input and Output

| Item | Meaning |
|---|---|
| Input | Strings `stamp` and `target` |
| Output | List of stamping positions |
| Initial string | All `'?'` |
| Goal | Construct `target` |
| Impossible case | Return `[]` |

Function shape:

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

## Examples

Example 1:

```python
stamp = "abc"
target = "ababc"
```

One valid process is:

Start:

```text
?????
```

Stamp at position `0`:

```text
abc??
```

Stamp at position `2`:

```text
ababc
```

So one valid answer is:

```python
[0, 2]
```

Example 2:

```python
stamp = "abca"
target = "aabcaca"
```

One valid answer is:

```python
[3, 0, 1]
```

These are the standard examples from the official problem. ([github.com](https://github.com/doocs/leetcode/blob/main/solution/0900-0999/0936.Stamping%20The%20Sequence/README_EN.md?utm_source=chatgpt.com))

## First Thought: Build the Target Forward

One idea is to simulate the construction directly.

Start from:

```text
?????
```

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:

```text
stamp  = "abc"
target = "ababc"
```

The substring:

```text
"abc"
```

can be erased into:

```text
"???"
```

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:

```python
m = len(stamp)
```

inside `target`, track:

| Item | Meaning |
|---|---|
| `made` | Positions already matching the stamp |
| `todo` | Positions still mismatching |

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:

```python
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:

```python
stamp = "abc"
target = "ababc"
```

Window size:

```python
3
```

Possible windows:

| Window | Substring | Matches stamp? |
|---|---|---|
| `0` | `"aba"` | No |
| `1` | `"bab"` | No |
| `2` | `"abc"` | Yes |

Window `2` can be erased immediately.

Erase:

```text
ab???
```

Now positions `2`, `3`, `4` are flexible.

This helps window `0`.

Window `0` becomes removable.

Erase:

```text
?????
```

Removal order:

```python
[2, 0]
```

Reverse it:

```python
[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:

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

| Metric | Value | Why |
|---|---|---|
| Time | `O(n * m)` | Each window and character interaction is processed a bounded number of times |
| Space | `O(n * m)` | Window dependency structures |

## Implementation

```python
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:

```python
done = [False] * n
```

For every window, we store:

```python
(made, todo)
```

`made` contains positions already matching the stamp.

`todo` contains positions still blocking removal.

If `todo` is empty:

```python
if not todo:
```

the window can immediately be erased.

We then mark all positions in that window as erased:

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

The queue stores newly erased positions.

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

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

If position `i` was blocking a window:

```python
if i in todo:
    todo.remove(i)
```

and the window now has no blockers:

```python
if not todo:
```

then it becomes removable.

Finally:

```python
return ans[::-1]
```

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

## Testing

```python
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()
```

| Test | Why |
|---|---|
| `"abc" -> "ababc"` | Standard example |
| `"abca" -> "aabcaca"` | Overlapping stamps |
| Impossible target | Must return empty list |
| Single-character stamp | Simplest repetitive case |