Stamping the Sequence [Hard] — Reverse Greedy Simulation

Problem Statement#

LeetCode 936 — Stamping the Sequence (Hard)

You are given two strings stamp and target. Imagine you have a blank sequence of n question marks ???...? (where n = target.length). In one move, you may place stamp over any contiguous window of s (where s = stamp.length) in the sequence, replacing every character in that window with the corresponding character from stamp.

Return any valid sequence of stamp positions (left-most index of each stamp placement) that converts the all-? sequence into target. If no such sequence exists within 10 * n moves, return an empty array.

Constraints:

• 1 <= stamp.length <= target.length <= 1000
• stamp and target consist only of lowercase English letters.
• The answer is guaranteed to need at most 10 * target.length stamps.

Worked Examples#

Example 1

stamp  = "abc"
target = "ababc"

One valid answer is [0, 2].

• Start: ?????
• Stamp at 0: abc??
• Stamp at 2: ababc ✓ (positions 2-4 are overwritten with "abc", covering the prior "c" at index 2)

Example 2

stamp  = "abca"
target = "aabcaca"

One valid answer is [3, 0, 1].

• Start: ???????
• Stamp at 3: ???abca (indices 3-6 = "abca")
• Stamp at 0: abca??? (indices 0-3 = "abca", overwrites index 3 with 'a')
• Stamp at 1: aabcaca (indices 1-4 = "abca", fills in the middle) ✓

Example 3

stamp  = "a"
target = "aaaaaa"

Answer: [0, 1, 2, 3, 4, 5] (stamp every position individually). When the stamp has length 1, every character must be stamped directly.

Why This Problem Matters#

LC 936 appears in Google, Amazon, and Microsoft interview loops. It is tagged Hard for a reason: the naive forward simulation — "try all possible stamp orderings and see which one reaches target" — is exponential in the worst case and dead on arrival in an interview.

What the interviewer is actually testing:

1. Problem inversion — Can you recognize when working backwards collapses an intractable forward search into a linear greedy sweep?
2. Greedy reasoning — Can you prove that a local greedy choice (stamp wherever a partial or full match exists right now) is globally safe?
3. Simulation discipline — Can you manage mutable state cleanly: tracking which characters have been resolved without off-by-one errors?
4. Termination analysis — Can you argue when the algorithm must terminate and when it should return an empty array?

This pattern — "reverse the operation, greedily undo steps, accumulate the reversed answer" — also appears in other Hard problems (see "This Pattern Solves" section). Mastering it here pays dividends across the entire problem set.

The Core Insight#

Why forward simulation fails#

Going forward, you have up to n - m + 1 possible positions to stamp at each step, and you might need up to 10n steps. Exploring all orderings is factorial — completely infeasible.

Why reverse simulation works#

Observe two facts about the final stamped string:

1. The last stamp placed must exactly match some window of target (because nothing overwrites it afterward).
2. Any stamp placed before the last stamp may have some of its characters later overwritten — meaning those earlier stamps only need to match the characters in their window that were not subsequently overwritten.

This gives us the reverse greedy: instead of laying stamps forward, we peel them off backward.

We maintain a working copy of target. We scan for any window of length m where:

• Every character either matches the stamp character at the same offset, or has already been erased (*).
• At least one character genuinely matches (not all * — that would mean we're stamping somewhere already fully erased, making no progress).

When we find such a window, we "un-stamp" it: replace all non-* characters in the window with *, record the position, and continue scanning.

We repeat sweeps until either:

• Every character in the working target is * — success! Reverse the recorded positions and return.
• A full sweep makes zero progress — the target is impossible; return [].

Why is this greedy safe? Because replacing characters with * only ever increases the number of windows that could match on the next sweep (wildcards match anything). A greedy un-stamp never prevents a future un-stamp. In other words: the order in which we un-stamp does not matter for correctness, only for the direction we record positions.

Visual Dry Run#

Let us trace stamp = "abca", target = "aabcaca" (length 7, stamp length 4).

Working target starts as: a a b c a c a

We scan all windows of length 4 (positions 0 through 3):

Let me re-trace with the correct window indexing (positions 0..3 for length-7 target, stamp length 4):

After sweep 2 position 0, the working target is * * * * * * a. One character remains.

All * — done! Recorded positions in order found: [1, 3, 0, 3]. Reversed: [3, 0, 3, 1].

One valid answer the LeetCode judge accepts: [3, 0, 1] (note there are multiple valid answers). The key insight visible in the trace: partial matches with wildcards do the heavy lifting — most windows only need to match a handful of real characters once surrounding stamps have erased the rest.

Common Mistakes#

Mistake 1 — Attempting forward BFS/DFS. The search space is (n - m + 1)^(10n) in the worst case. Candidates who reach for BFS will time-out on any input with n > 10. The moment the problem says "find any valid sequence within 10n moves," that's a signal to think greedy/reverse, not exhaustive search.

Mistake 2 — Only accepting full matches in the reverse sweep. A window like a * b * against stamp a c b d is a valid partial match (two real characters match, two are wildcards). If you require all four characters to match, you will miss valid un-stamp positions and falsely return []. The rule is: every non-* character in the window must equal the corresponding stamp character; at least one non-* character must exist.

Mistake 3 — Counting a window as valid when it is all *. The all-* window passes the "every non-* matches" check vacuously, but recording it makes no progress (no new characters are converted to *). This causes an infinite loop. Always require replaced >= 1 (at least one real character was erased).

Mistake 4 — Forgetting to reverse the result. The algorithm finds stamps in reverse chronological order (last stamp first). Returning positions in found-order gives the wrong sequence. The final step must be positions[::-1] (Python) or positions.reverse() (JavaScript).

Mistake 5 — Off-by-one in the scan range. Valid stamp positions run from 0 to n - m inclusive (n - m + 1 positions total). Using range(n - m) in Python (stopping one short) or i < n - m in JavaScript silently skips the last valid position and can cause spurious failures on inputs where the match sits at the end of the string.

Mistake 6 — Mutating the original string instead of a list. Python strings are immutable. Doing target[i] = '*' on a raw string raises a TypeError. Convert to list(target) before the loop. In JavaScript, working with target.split('') achieves the same effect.

Mistake 7 — Not checking for impossibility. If a full sweep of all n - m + 1 positions makes zero replacements but the target is not yet all *, the input is impossible (or you have a bug). Returning whatever partial answer you have is wrong. Check for made_progress == False and return [].

Solutions#

Python#

def movesToStamp(stamp: str, target: str) -> list[int]:
    m = len(stamp)          # stamp length
    n = len(target)         # target length
    target = list(target)   # make mutable; we'll overwrite chars with '*'
    result = []             # stores positions in reverse chronological order
    total_replaced = 0      # how many target chars have been converted to '*'
 
    def try_stamp(pos: int) -> int:
        """
        Try to un-stamp at position pos.
        Returns the number of NEW characters replaced (0 = not a valid match).
        """
        replaced = 0  # count of real (non-'*') chars that match stamp
 
        # First pass: check if this window is a valid match
        for i in range(m):
            if target[pos + i] == '*':
                continue            # wildcard — will match anything, skip check
            if target[pos + i] != stamp[i]:
                return 0            # mismatch — cannot un-stamp here
            replaced += 1           # genuine matching character
 
        # If replaced == 0, the entire window is already '*' — no progress
        if replaced == 0:
            return 0
 
        # Second pass: erase all non-'*' characters in this window
        for i in range(m):
            if target[pos + i] != '*':
                target[pos + i] = '*'
 
        return replaced
 
    # Keep sweeping until the whole target is '*'
    while total_replaced < n:
        made_progress = False
 
        for pos in range(n - m + 1):       # scan every valid stamp position
            r = try_stamp(pos)
            if r > 0:
                total_replaced += r         # mark progress
                result.append(pos)          # record this position (reversed order)
                made_progress = True
 
        if not made_progress:
            return []                       # stuck — target is impossible
 
    # result was collected in reverse chronological order; flip it
    return result[::-1]

JavaScript#

/**
 * @param {string} stamp
 * @param {string} target
 * @return {number[]}
 */
function movesToStamp(stamp, target) {
    const m = stamp.length;
    const n = target.length;
    const chars = target.split('');   // mutable char array
    const result = [];                // positions in reverse chronological order
    let totalReplaced = 0;            // chars converted to '*' so far
 
    /**
     * Try to un-stamp at position pos.
     * Returns the count of new '*' replacements (0 = invalid position).
     */
    function tryStamp(pos) {
        let replaced = 0;
 
        // First pass: validate the window
        for (let i = 0; i < m; i++) {
            if (chars[pos + i] === '*') {
                continue;               // wildcard matches anything — skip
            }
            if (chars[pos + i] !== stamp[i]) {
                return 0;               // real mismatch — cannot un-stamp here
            }
            replaced++;                 // genuine match
        }
 
        // All wildcards and no real matches → no progress
        if (replaced === 0) return 0;
 
        // Second pass: erase matched characters
        for (let i = 0; i < m; i++) {
            if (chars[pos + i] !== '*') {
                chars[pos + i] = '*';
            }
        }
 
        return replaced;
    }
 
    // Sweep until target is fully erased or we get stuck
    while (totalReplaced < n) {
        let madeProgress = false;
 
        for (let pos = 0; pos <= n - m; pos++) {   // n - m inclusive
            const r = tryStamp(pos);
            if (r > 0) {
                totalReplaced += r;
                result.push(pos);                   // reverse chronological
                madeProgress = true;
            }
        }
 
        if (!madeProgress) return [];               // impossible input
    }
 
    // Reverse to get forward chronological stamp order
    return result.reverse();
}

Complexity Analysis#

In practice the algorithm is fast: each sweep makes substantial progress (erasing multiple characters per match), and the constant factor is small. The theoretical worst case rarely materializes on real inputs.

Follow-up Questions#

Q1: Can you reconstruct the forward stamp sequence uniquely? No. Multiple valid orderings usually exist, and the problem only asks for any valid one. The reverse greedy does not generally produce the lexicographically smallest or any other canonical ordering.

Q2: What if stamp.length > target.length? Impossible by constraint — the stamp can never be placed if it exceeds the target length. Return [] immediately.

Q3: What if the stamp itself contains repeated characters? The algorithm handles this transparently — repeated characters in the stamp are treated the same as any other characters during window matching. No special case is needed.

Q4: Can you prove correctness formally? Yes. By induction: the last stamp placed in any valid sequence leaves an exact full match in target. Un-stamping that match (replacing with *) reduces the problem to a strictly smaller instance. Wildcard propagation ensures earlier stamps — whose characters may be overwritten by later ones — are still discoverable as partial matches. This induction shows the greedy always finds a solution when one exists.

Q5: Could you solve this with BFS on a state graph? In principle, yes — the state is the current string, edges are stamp operations, and the goal is the target. But the state space is 26^n (all possible strings of length n), making BFS completely intractable for n > 5 or so. The reverse greedy is the only practical approach.

Q6: What is the maximum number of stamps the algorithm records? At most 10 * n stamps, as guaranteed by the problem. In the worst case every stamp placement converts only one character, giving n stamps. The 10n bound gives headroom for repeated partial matches.

This Pattern Solves#

The reverse simulation + greedy un-do pattern shows up across multiple Hard problems:

When you see "reconstruct a sequence of operations that produces a result," always ask: "Is it easier to undo operations backward than to build forward?" If each undo step is locally deterministic and irreversible states can be represented as wildcards, reverse simulation is the right tool.

Key Takeaways#

• Work backwards: scan the target for positions where every non-wildcard character matches the stamp, "erase" those characters to *, and record the stamp position. Repeat until all characters are wildcards.
• Wildcards (*) match any character during reverse simulation — this is safe because future (earlier in forward order) stamps will overwrite those positions.
• The algorithm requires at most O(n * m) total passes where n = len(target) and m = len(stamp). Each pass is O(m) per position, O(n) positions = O(n * m) time.
• A full pass with no progress means the sequence is impossible — return an empty list.
• Reverse the recorded stamp positions at the end: the first stamp applied (forward) is the last recorded (backward).
• The "partial match with wildcards" insight is the core: accepting partial matches never blocks future progress and always opens up more future matches.
• This is the only LC 936 approach that avoids exponential backtracking — the reverse greedy converts a hard forward planning problem into a simple backward simulation.