Problem Description

In the Stamping The Sequence problem, you are given two strings: stamp and target, both consisting of lowercase English letters.

• You can "stamp" the stamp string onto the target string at any position, as long as each character in stamp either matches the corresponding character in target or the corresponding character in target is already a question mark ('?').
• When you stamp, every character in target at that position is replaced with '?'.
• Your goal is to convert the entire target string into all question marks ('?') using the minimum number of stamping moves.
• Return an array of the positions where you stamped, in the order you performed the stamps. If it's not possible, return an empty array.
• It is guaranteed that there is at least one valid answer. You may return any valid answer.

Constraints:

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

Thought Process

At first glance, it may seem natural to try stamping from left to right, greedily matching as many characters as possible. However, this can quickly run into situations where future required matches become impossible due to earlier moves.

Instead, consider the problem in reverse: what if we try to "unstamp" the target string back to all question marks? If we can repeatedly find substrings that could have been produced by stamping (i.e., they match the stamp or are already '?'), we can replace them with question marks, and keep track of the positions. Reversing the order of these positions gives us a valid stamping sequence.

This reverse approach is more robust because it avoids getting stuck due to premature stamping, and ensures that every move is valid with respect to the current state of the target.

Solution Approach

The solution uses a greedy, reverse simulation. Here’s how we approach it step by step:

1. Initialization:
   • Convert target into a mutable list for easy modification.
   • Track which positions have already been stamped to avoid redundant work.
   • Keep a counter for how many characters have been turned into '?'.
2. Main Loop:
   • While not all characters in target are '?':
   • For every possible position where stamp could fit in target:
   • If this window hasn't been stamped before and can be stamped now (i.e., all non-'?' characters match stamp):
   • Replace all characters in this window with '?'.
   • Record this position.
   • Update the count of question marks.
   • Mark this window as stamped.
   • If no progress is made in a full pass, return an empty array (impossible case).
3. Result:
   • Since we worked backwards, reverse the list of positions before returning.

Why this works: By always stamping windows that can be fully erased (i.e., all their remaining letters match the stamp or are already '?'), we guarantee that every move is valid and that we eventually erase the entire target.

Example Walkthrough

Input: stamp = "abc", target = "ababc"

• Initial target: ababc
• Possible stamp positions: 0, 1, 2
• First, at position 1: bab matches abc only if we ignore the first character. But at position 0: aba matches abc only in the first two letters.
• Instead, by reverse simulation, we look for a window that could be erased. At position 2: abc matches abc exactly. We stamp at position 2, turning target into ab???.
• Now, at position 0: ab? can be stamped, since ab? matches abc in the first two letters and the last is already '?'. We stamp at position 0, turning target into ?????.
• We have fully erased the target. Stamping sequence (in reverse order): [2, 0]. So we return [0, 2].

Time and Space Complexity

• Brute-force approach:
  • Would try all possible stamping sequences, leading to exponential time complexity (very slow and impractical for large inputs).
• Optimized approach (reverse simulation):
  • In each outer loop iteration, we potentially stamp at least one new position, so at most O(N) iterations, where N is the length of target.
  • For each iteration, we check each possible window of size M (length of stamp), so O(N * M) per iteration.
  • Total time complexity: O(N^2 * M) in the worst case.
  • Space complexity: O(N) for storing the mutable target and the result positions.

Summary

The key insight for this problem is to work backwards, repeatedly "unstamping" any window that could have been produced by a valid stamping move. This ensures that every move is legal and avoids getting stuck. By tracking the positions and reversing the result, we obtain a valid stamping sequence that transforms target into all question marks. This approach is both efficient and elegant, leveraging greedy matching and careful state tracking.

Code Implementation

class Solution:
    def movesToStamp(self, stamp: str, target: str):
        S, T = list(stamp), list(target)
        slen, tlen = len(stamp), len(target)
        res = []
        visited = [False] * (tlen - slen + 1)
        stars = 0

        def can_stamp(pos):
            changed = False
            for i in range(slen):
                if T[pos + i] == '?':
                    continue
                if T[pos + i] != S[i]:
                    return False
                changed = True
            return changed

        def do_stamp(pos):
            nonlocal stars
            for i in range(slen):
                if T[pos + i] != '?':
                    T[pos + i] = '?'
                    stars += 1

        while stars < tlen:
            stamped = False
            for i in range(tlen - slen + 1):
                if not visited[i] and can_stamp(i):
                    do_stamp(i)
                    visited[i] = True
                    res.append(i)
                    stamped = True
            if not stamped:
                return []
        return res[::-1]
      

class Solution {
public:
    vector<int> movesToStamp(string stamp, string target) {
        int slen = stamp.size(), tlen = target.size();
        vector<char> T(target.begin(), target.end());
        vector<bool> visited(tlen - slen + 1, false);
        vector<int> res;
        int stars = 0;

        auto can_stamp = [&](int pos) {
            bool changed = false;
            for (int i = 0; i < slen; ++i) {
                if (T[pos + i] == '?') continue;
                if (T[pos + i] != stamp[i]) return false;
                changed = true;
            }
            return changed;
        };

        auto do_stamp = [&](int pos) {
            for (int i = 0; i < slen; ++i) {
                if (T[pos + i] != '?') {
                    T[pos + i] = '?';
                    ++stars;
                }
            }
        };

        while (stars < tlen) {
            bool stamped = false;
            for (int i = 0; i <= tlen - slen; ++i) {
                if (!visited[i] && can_stamp(i)) {
                    do_stamp(i);
                    visited[i] = true;
                    res.push_back(i);
                    stamped = true;
                }
            }
            if (!stamped) return {};
        }
        reverse(res.begin(), res.end());
        return res;
    }
};
      

class Solution {
    public int[] movesToStamp(String stamp, String target) {
        char[] S = stamp.toCharArray();
        char[] T = target.toCharArray();
        int slen = S.length, tlen = T.length;
        boolean[] visited = new boolean[tlen - slen + 1];
        List<Integer> res = new ArrayList<>();
        int stars = 0;

        while (stars < tlen) {
            boolean stamped = false;
            for (int i = 0; i <= tlen - slen; i++) {
                if (!visited[i] && canStamp(T, i, S)) {
                    stars += doStamp(T, i, S.length);
                    visited[i] = true;
                    res.add(i);
                    stamped = true;
                }
            }
            if (!stamped) return new int[0];
        }
        int[] ans = new int[res.size()];
        for (int i = 0; i < res.size(); i++) {
            ans[i] = res.get(res.size() - 1 - i);
        }
        return ans;
    }

    private boolean canStamp(char[] T, int pos, char[] S) {
        boolean changed = false;
        for (int i = 0; i < S.length; i++) {
            if (T[pos + i] == '?') continue;
            if (T[pos + i] != S[i]) return false;
            changed = true;
        }
        return changed;
    }

    private int doStamp(char[] T, int pos, int slen) {
        int count = 0;
        for (int i = 0; i < slen; i++) {
            if (T[pos + i] != '?') {
                T[pos + i] = '?';
                count++;
            }
        }
        return count;
    }
}
      

var movesToStamp = function(stamp, target) {
    const S = stamp.split(''), T = target.split('');
    const slen = S.length, tlen = T.length;
    const visited = new Array(tlen - slen + 1).fill(false);
    const res = [];
    let stars = 0;

    function canStamp(pos) {
        let changed = false;
        for (let i = 0; i < slen; i++) {
            if (T[pos + i] === '?') continue;
            if (T[pos + i] !== S[i]) return false;
            changed = true;
        }
        return changed;
    }

    function doStamp(pos) {
        for (let i = 0; i < slen; i++) {
            if (T[pos + i] !== '?') {
                T[pos + i] = '?';
                stars++;
            }
        }
    }

    while (stars < tlen) {
        let stamped = false;
        for (let i = 0; i <= tlen - slen; i++) {
            if (!visited[i] && canStamp(i)) {
                doStamp(i);
                visited[i] = true;
                res.push(i);
                stamped = true;
            }
        }
        if (!stamped) return [];
    }
    return res.reverse();
};