Stamping The Sequence

Stamping The Sequence looks impossible forwards — overlapping stamps overwrite each other, so you cannot reason about the final string left to right. The trick is one of the most elegant moves in interviews: run the process in reverse.

The slow way first

Forwards, every choice of where to stamp affects every later choice, because a later stamp can overwrite an earlier one. There is no clean greedy rule and the search tree explodes. Trying to build the target by stamping is a combinatorial mess.

The question to ask: what does the very last stamp look like? Whatever it was, it left a clean, untouched copy of stamp somewhere in target. So the last stamp is easy to spot — and if we peel it off, the next-to-last becomes easy too.

The idea: un-stamp instead of stamp

Work backwards. Scan target for any window that equals the stamp, where an already-erased ? counts as a wildcard match. Replace that window with ? and record its start index. Repeat until the whole string is ?. The starts we recorded are the un-stamp order; reverse them to get the build order.

The key insight: matching against ? as a wildcard lets later (overlapping) stamps be erased even when earlier ones already chewed up part of the window.

Walk through it

Step through the animation. With target = "abab", the window at index 0 matches "ab", so we erase it to "??ab" and record 0. The window at index 2 still matches "ab", so we erase it to "????" and record 2. Everything is ?, so we stop. We un-stamped in order [0, 2]; reversed, the build order is [2, 0].

Pseudocode

t = list(target); stamps = []; total erased = 0
while not everything is "?":
    stamped this pass = false
    for each window start i:
        if window matches stamp (treating ? as wildcard, and not already all ?):
            erase the window to ?, add its newly-erased count to total
            record i; mark stamped this pass = true
    if no window stamped this pass:
        return []          # impossible
return recorded starts reversed

The Python solution

def moves_to_stamp(stamp, target):
    t = list(target)
    stamps, total = [], 0
    while total < len(t):
        stamped = False
        for i in range(len(t) - len(stamp) + 1):
            if can_stamp(t, stamp, i):
                total += do_stamp(t, stamp, i)
                stamps.append(i)
                stamped = True
        if not stamped:
            return []
    return stamps[::-1]

• t is the mutable target; total counts how many characters have been turned into ?.
• can_stamp returns true if window i has at least one non-? char and every non-? char equals the stamp — ? positions match anything.
• do_stamp erases the window to ? and returns how many newly erased characters it added, which we accumulate into total.
• If a full pass stamps nothing but the string is not all ?, the target is unreachable, so we return [].
• Line 13 reverses the recorded starts: un-stamp order reversed is the order to build the target.

Complexity

Every pass erases at least one stamp worth of characters, so there are at most O(n/m) passes, each scanning O(n*m) work — O(n^2) total. The space is the mutable copy of the target plus the recorded starts.

When this pattern shows up

Practice