Skip to main content

936 - Stamping The Sequence

Difficulty: Hard | Pattern: Greedy (Reverse Simulation) | Company tags: Google

Problem Statement​

You are given two strings stamp and target. Initially, there is a string s of '?' characters with the same length as target.

In one move, you may place stamp over s and replace every letter in s at that stamp position with the corresponding letter from stamp.

Return an array of the index of the left-most letter being stamped at each move so that we can query s == target. If the task is impossible, return an empty array.

Example 1:

Input: stamp = "abc", target = "ababc"
Output: [0,2]

Approach: Reverse Greedy — O(n × m)​

Key insight: Work backwards. Instead of placing stamps on ?, find positions where stamp matches target (potentially with wildcards ?) and "un-stamp" by replacing matched positions with ?. Repeat until target is all ?.

def movesToStamp(stamp: str, target: str) -> list[int]:
    m, n = len(stamp), len(target)
    target = list(target)
    result = []
    total_replaced = 0
    
    def try_stamp(pos):
        nonlocal total_replaced
        replaced = 0
        for i in range(m):
            if target[pos + i] == '?':
                continue
            if target[pos + i] != stamp[i]:
                return 0
            replaced += 1
        # Stamp here — replace with '?'
        for i in range(m):
            if target[pos + i] != '?':
                target[pos + i] = '?'
        return replaced
    
    while total_replaced < n:
        stamped = False
        for pos in range(n - m + 1):
            replaced = try_stamp(pos)
            if replaced:
                total_replaced += replaced
                result.append(pos)
                stamped = True
        if not stamped:
            return []
    
    result.reverse()
    return result

Key Insight: Why Reverse?​

In the forward direction, stamps can overlap in complex ways. In reverse, we look for positions where stamp matches the current state (with some already-reversed ? wildcards). Reversing the sequence gives the forward order.

Complexity​

  • Time: O(n × m) per round, O(n/m) rounds → O(n²) worst case
  • Space: O(n)