# Stamping The Sequence
**Difficulty:** HARD
[External](https://leetcode.com/problems/stamping-the-sequence)
Canonical: https://scaleengineer.com/dsa/problems/stamping-the-sequence
**Patterns:** [Greedy](https://scaleengineer.com/dsa/patterns/greedy)
**Data structures:** String, Stack, Queue
**Companies:** [Morgan Stanley](https://scaleengineer.com/companies/morgan-stanley)
---
## Problem
You are given two strings `stamp` and `target`. Initially, there is a string `s` of length `target.length` with all `s[i] == '?'`.

In one turn, you can place `stamp` over `s` and replace every letter in the `s` with the corresponding letter from `stamp`.

* For example, if `stamp = "abc"` and `target = "abcba"`, then `s` is `"?????"` initially. In one turn you can:  
  * place `stamp` at index `0` of `s` to obtain `"abc??"`,
  * place `stamp` at index `1` of `s` to obtain `"?abc?"`, or
  * place `stamp` at index `2` of `s` to obtain `"??abc"`.  
Note that `stamp` must be fully contained in the boundaries of `s` in order to stamp (i.e., you cannot place `stamp` at index `3` of `s`).

We want to convert `s` to `target` using **at most** `10 * target.length` turns.

Return _an array of the index of the left-most letter being stamped at each turn_. If we cannot obtain `target` from `s` within `10 * target.length` turns, return an empty array.

**Example 1:**

**Input:** stamp = "abc", target = "ababc"
**Output:** [0,2]
**Explanation:** Initially s = "?????".
- Place stamp at index 0 to get "abc??".
- Place stamp at index 2 to get "ababc".
[1,0,2] would also be accepted as an answer, as well as some other answers.

**Example 2:**

**Input:** stamp = "abca", target = "aabcaca"
**Output:** [3,0,1]
**Explanation:** Initially s = "???????".
- Place stamp at index 3 to get "???abca".
- Place stamp at index 0 to get "abcabca".
- Place stamp at index 1 to get "aabcaca".

**Constraints:**

* `1 <= stamp.length <= target.length <= 1000`
* `stamp` and `target` consist of lowercase English letters.

# Approaches
## Brute-force Greedy Backward Search
This approach simulates the stamping process in reverse. Instead of building the `target` string from a string of question marks, we start with the `target` string and try to 'un-stamp' it back to a string of all question marks. The core idea is that the last stamp applied must have perfectly matched a substring of the final `target`. By repeatedly finding such matches and replacing them with question marks, we can reverse the entire process.
**Time:** O(N * (N-M) * M), where N is the length of `target` and M is the length of `stamp`. The outer `while` loop can run up to N times in the worst case (if we only replace one character at a time). Inside the loop, we iterate through `N-M` possible windows, and for each window, we perform a check and a replacement, both taking O(M) time. This leads to a cubic complexity in the worst-case scenarios. · **Space:** O(N), where N is the length of `target`. This space is used to store the character array for the target, the result list, and the visited array.
**Pros:** Relatively simple to understand and implement.; Low space complexity.
**Cons:** The time complexity is high, potentially leading to a 'Time Limit Exceeded' error on larger inputs.
### Explanation
The algorithm works by repeatedly scanning the `target` string for substrings that could have been placed by the `stamp`. When such a substring is found, it's replaced with `'?'` characters, signifying that this part of the `target` is now 'explained'. This process continues until the entire string becomes `'?'`s. The indices of these replacements, when reversed, give a valid sequence of stamping operations.

```java
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

class Solution {
    public int[] movesToStamp(String stamp, String target) {
        char[] sChars = stamp.toCharArray();
        char[] tChars = target.toCharArray();
        int n = tChars.length;
        int m = sChars.length;
        List<Integer> result = new ArrayList<>();
        boolean[] visited = new boolean[n - m + 1];
        int stars = 0;

        while (stars < n) {
            boolean replacedInRound = false;
            for (int i = 0; i <= n - m; i++) {
                if (!visited[i] && canReplace(tChars, i, sChars)) {
                    int newStars = doReplace(tChars, i, m);
                    if (newStars > 0) {
                        stars += newStars;
                        replacedInRound = true;
                        visited[i] = true;
                        result.add(i);
                    }
                }
            }
            if (!replacedInRound) {
                return new int[0];
            }
        }

        Collections.reverse(result);
        return result.stream().mapToInt(i -> i).toArray();
    }

    private boolean canReplace(char[] tChars, int start, char[] sChars) {
        for (int i = 0; i < sChars.length; i++) {
            if (tChars[start + i] != '?' && tChars[start + i] != sChars[i]) {
                return false;
            }
        }
        return true;
    }

    private int doReplace(char[] tChars, int start, int len) {
        int count = 0;
        for (int i = 0; i < len; i++) {
            if (tChars[start + i] != '?') {
                tChars[start + i] = '?';
                count++;
            }
        }
        return count;
    }
}
```
### Algorithm
*   Initialize a character array `tChars` from the `target` string, a list `result` to store stamp indices, and a count `stars` of characters replaced by '?'.
*   Create a boolean array `visited` of size `target.length - stamp.length + 1` to avoid processing the same window multiple times.
*   Loop continuously as long as progress is made in a round (`stars < target.length`):
    *   Set a flag `replacedInRound` to `false` at the beginning of each pass.
    *   Iterate through all possible starting positions `i` for the stamp from `0` to `n-m`.
    *   If window `i` has not been `visited` and can be 'unstamped', proceed.
    *   A window can be unstamped if every character in the window either matches the corresponding character in `stamp` or is already a '?'.
    *   If a valid window is found at `i`, replace the characters in that window with '?', add `i` to the `result` list, mark `i` as visited, and update the `stars` count. Only add `i` to the result if at least one new character was replaced to ensure progress.
    *   Set `replacedInRound` to `true`.
    *   If a full pass over all windows yields no new unstamps (`replacedInRound` remains `false`), then it's impossible to solve.
*   If the loop completes and `stars` equals the length of `target`, it means we have successfully converted the entire string to '?'. The sequence of operations is the `result` list in reverse order.
*   If it's impossible, return an empty array.

## Optimized Greedy Backward Search with a Queue
This approach significantly optimizes the brute-force method by avoiding redundant checks. Instead of scanning the entire string repeatedly, we identify which windows are ready to be 'unstamped' and process them in a queue. An unstamp operation at one position can make adjacent or overlapping windows ready. We track these dependencies to efficiently find the next window to process.
**Time:** O(N*M), where N is the length of `target` and M is the length of `stamp`. The initialization phase takes O((N-M)*M) to compute `todo` counts and build the `affects` map. The processing phase is also O(N*M) in total, because each character `k` is marked `done` once, and when it is, we iterate through `affects[k]`, which has size at most M. The total work across all characters is bounded by the total number of dependencies, which is (N-M+1)*M. · **Space:** O(N*M) to store the `affects` dependency map. In the worst case (e.g., M is close to N/2), this can be substantial. Other data structures like `todo`, `queue`, and `done` take O(N) space.
**Pros:** Significantly more time-efficient than the brute-force approach.; Guaranteed to pass within the time limits for the given constraints.
**Cons:** Requires more complex data structures.; Has a higher space complexity, which could be a concern for very large inputs, though it's acceptable for the given constraints.
### Explanation
This optimized method avoids the expensive re-scanning of the entire string. It first preprocesses the `target` to understand the relationships between character positions and stamp windows.

Specifically, for each possible stamp window, we count how many characters currently mismatch the `stamp`. These are windows that are not yet ready. For each character position, we also list all windows that cover it. When a window becomes ready (mismatches drop to zero), we process it. Processing involves marking its characters as `?`, and for each newly marked `?`, we update the mismatch count of all other windows that covered this character. This might make new windows ready, which are then added to a queue for processing.

```java
import java.util.ArrayList;
import java.util.Collections;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

class Solution {
    public int[] movesToStamp(String stamp, String target) {
        int m = stamp.length();
        int n = target.length();
        char[] sChars = stamp.toCharArray();
        char[] tChars = target.toCharArray();

        List<Integer>[] affects = new ArrayList[n];
        for (int i = 0; i < n; i++) {
            affects[i] = new ArrayList<>();
        }

        int[] todo = new int[n - m + 1];
        Queue<Integer> queue = new LinkedList<>();
        boolean[] visited = new boolean[n - m + 1];

        for (int i = 0; i <= n - m; i++) {
            for (int j = 0; j < m; j++) {
                if (tChars[i + j] != sChars[j]) {
                    todo[i]++;
                }
            }
            if (todo[i] == 0) {
                queue.offer(i);
                visited[i] = true;
            }
            for (int j = 0; j < m; j++) {
                affects[i + j].add(i);
            }
        }

        List<Integer> result = new ArrayList<>();
        boolean[] done = new boolean[n];
        int stampedCount = 0;

        while (!queue.isEmpty()) {
            int i = queue.poll();
            result.add(i);

            for (int j = 0; j < m; j++) {
                int k = i + j;
                if (!done[k]) {
                    done[k] = true;
                    stampedCount++;
                    for (int p : affects[k]) {
                        if (!visited[p]) {
                            todo[p]--;
                            if (todo[p] == 0) {
                                queue.offer(p);
                                visited[p] = true;
                            }
                        }
                    }
                }
            }
        }

        if (stampedCount != n) {
            return new int[0];
        }

        Collections.reverse(result);
        return result.stream().mapToInt(i -> i).toArray();
    }
}
```
### Algorithm
*   **Initialization**:
    *   Create a `todo` array, where `todo[i]` stores the number of characters in the window starting at `i` that do not match the `stamp`.
    *   Create a dependency map `affects`, where `affects[p]` is a list of all window indices that cover character position `p`.
    *   Initialize a queue and add all window indices `i` that are ready from the start (i.e., `todo[i] == 0`). Mark these as visited.
*   **Processing**:
    *   While the queue is not empty, dequeue a window index `i`. This is a window we are 'unstamping'. Add `i` to the result list.
    *   For each character position `p` within the window `i`:
        *   If `p` has not been stamped to '?' yet, mark it as done.
        *   This change might make other windows ready. For every window `j` that is affected by the change at `p` (i.e., `j` is in `affects[p]`):
            *   Decrement `todo[j]`.
            *   If `todo[j]` becomes 0, it means window `j` is now a perfect match with the (partially '?'d) string. Add `j` to the queue and mark it as visited.
*   **Finalization**:
    *   After the queue is empty, check if all `N` characters have been turned to '?'.
    *   If yes, the `result` list contains the sequence of stamp indices in reverse order. Reverse it and return.
    *   If not, a solution is not possible, so return an empty array.

# Solutions
### Java

```java
class Solution {
public
  int[] movesToStamp(String stamp, String target) {
    int m = stamp.length(), n = target.length();
    int[] indeg = new int[n - m + 1];
    Arrays.fill(indeg, m);
    List<Integer>[] g = new List[n];
    Arrays.setAll(g, i->new ArrayList<>());
    Deque<Integer> q = new ArrayDeque<>();
    for (int i = 0; i < n - m + 1; ++i) {
      for (int j = 0; j < m; ++j) {
        if (target.charAt(i + j) == stamp.charAt(j)) {
          if (--indeg[i] == 0) {
            q.offer(i);
          }
        } else {
          g[i + j].add(i);
        }
      }
    }
    List<Integer> ans = new ArrayList<>();
    boolean[] vis = new boolean[n];
    while (!q.isEmpty()) {
      int i = q.poll();
      ans.add(i);
      for (int j = 0; j < m; ++j) {
        if (!vis[i + j]) {
          vis[i + j] = true;
          for (int k : g[i + j]) {
            if (--indeg[k] == 0) {
              q.offer(k);
            }
          }
        }
      }
    }
    for (int i = 0; i < n; ++i) {
      if (!vis[i]) {
        return new int[0];
      }
    }
    Collections.reverse(ans);
    return ans.stream().mapToInt(Integer : : intValue).toArray();
  }
}

```

### CPP

```cpp
class Solution {
public:
  vector<int> movesToStamp(string stamp, string target) {
    int m = stamp.size(), n = target.size();
    vector<int> indeg(n - m + 1, m);
    vector<int> g[n];
    queue<int> q;
    for (int i = 0; i < n - m + 1; ++i) {
      for (int j = 0; j < m; ++j) {
        if (target[i + j] == stamp[j]) {
          if (--indeg[i] == 0) {
            q.push(i);
          }
        } else {
          g[i + j].push_back(i);
        }
      }
    }
    vector<int> ans;
    vector<bool> vis(n);
    while (q.size()) {
      int i = q.front();
      q.pop();
      ans.push_back(i);
      for (int j = 0; j < m; ++j) {
        if (!vis[i + j]) {
          vis[i + j] = true;
          for (int k : g[i + j]) {
            if (--indeg[k] == 0) {
              q.push(k);
            }
          }
        }
      }
    }
    for (int i = 0; i < n; ++i) {
      if (!vis[i]) {
        return {};
      }
    }
    reverse(ans.begin(), ans.end());
    return ans;
  }
};

```

### Python

```python
class Solution:
    def movesToStamp(self, stamp: str, target: str) -> List[int]: m, n = len(stamp), len(target) indeg = [m] * (n - m + 1) q = deque() g = [[] for _ in range(n)] for i in range(n - m + 1): for j, c in enumerate(stamp): if target[i + j] == c: indeg[i] -= 1 if indeg[i] == 0: q . append(i) else: g[i + j]. append(i) ans = [] vis = [False] * n while q: i = q . popleft() ans . append(i) for j in range(m): if not vis[i + j]: vis[i + j] = True for k in g[i + j]: indeg[k] -= 1 if indeg[k] == 0: q . append(k) return ans[:: - 1] if all(vis) else []

```