LeetCode 936 - Stamping The Sequence

LeetCode Problem 936

Difficulty: 🔴 Hard
Topics: String, Stack, Greedy, Queue

Solution

Problem Understanding

This problem asks us to reconstruct a target string by repeatedly applying a smaller string called stamp.

We begin with a string s that has the same length as target, but every character is initially '?'. In one operation, we may place the stamp string onto any valid position in s, and doing so overwrites the characters in that range with the characters from stamp.

The goal is to produce the exact target string using at most 10 * target.length stamping operations.

The output is not the final string itself, but rather the sequence of starting indices where the stamp was applied. The sequence should describe the stamping order from the initial all-question-mark string to the final target string.

A direct forward simulation is difficult because many different stamping orders may work, and later stamps can overwrite earlier characters. Instead, the key observation is that reversing the process is much easier.

Rather than building the target from '?', we can start from target and repeatedly replace valid stamp-shaped regions with '?' until the entire string becomes question marks.

The constraints are important:

• target.length <= 1000
• stamp.length <= target.length

This size is small enough for an O(n^2) style algorithm, but too large for exponential backtracking or brute-force search.

Several edge cases are important:

• The target may already equal the stamp.
• Some characters may require overlapping stamps.
• Some targets cannot be formed at all.
• Multiple valid answers may exist.
• A stamp operation in reverse must replace at least one non-question-mark character, otherwise we could loop forever.

Approaches

Brute Force Approach

A naive approach would attempt to construct the target string from left to right.

At every step, we could try stamping at every possible position and check whether it helps us move closer to the target. This quickly becomes difficult because stamps may overlap and overwrite previous characters. A locally valid move may later make the construction impossible.

One possible brute-force strategy is backtracking:

1. Try every possible stamp position.
2. Apply the stamp.
3. Recursively continue.
4. Backtrack if the current path fails.

This approach is correct because it explores all possible sequences of stamping operations. However, the number of possible sequences grows exponentially with the target length.

Since the target length can be up to 1000, exhaustive search is completely infeasible.

Optimal Greedy Reverse Simulation

The key insight is that reversing the process is much easier than constructing it forward.

Instead of starting with '?????' and building the target, we start with target and try to erase it back into question marks.

Suppose a substring matches the stamp, or matches the stamp except for some characters already replaced by '?'. Then that substring could have been produced by a stamp operation earlier. Therefore, we can safely replace all characters in that region with '?'.

This naturally leads to a greedy process:

• Find a window where stamping is possible.
• Replace its characters with '?'.
• Record the index.
• Repeat until the whole string becomes '?'.

Because we are reversing operations, the recorded indices must be reversed before returning.

The crucial rule is that each reverse stamping operation must replace at least one real character. Otherwise, we could repeatedly stamp the same all-question-mark region forever.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	Exponential	Exponential	Tries all stamping sequences recursively
Optimal	O((N - M + 1) * N * M)	O(N)	Greedy reverse stamping with repeated scans

Here:

• N = len(target)
• M = len(stamp)

Algorithm Walkthrough

1. Convert the target string into a mutable character array.

Since strings are immutable in Python and Go, we need a mutable representation so we can replace characters with '?'. 2. Maintain a visited array for stamp positions.

Once a window has already been processed, we do not need to process it again. 3. Repeatedly scan every possible stamp position.

For each position i, check whether the stamp can be applied in reverse. 4. A reverse stamp is valid if:

• Every non-question-mark character matches the stamp character.
• At least one character in the window is not already '?'.

The second condition prevents infinite loops. 5. If a valid window is found:

• Replace all characters in that window with '?'.
• Count how many new characters were erased.
• Record the position.
• Mark the window as visited.

6. Continue scanning until either:

• All characters become '?', or
• No progress can be made in an entire pass.

7. If all characters were erased, reverse the recorded positions and return them.

Since we processed the target backward, reversing restores the original stamping order. 8. If we get stuck before erasing everything, return an empty array.

Why it works

The algorithm works because every reverse stamping operation corresponds to a valid forward stamping operation.

Whenever a window matches the stamp except for already-erased characters, that window must have been stampable at some earlier point in the forward process. Replacing it with '?' is therefore safe.

The algorithm only removes characters when doing so makes real progress, guaranteeing termination. If the algorithm cannot erase the entire target, then no valid stamping sequence exists.

Python Solution

from typing import List

class Solution:
    def movesToStamp(self, stamp: str, target: str) -> List[int]:
        stamp_len = len(stamp)
        target_len = len(target)

        target_chars = list(target)

        visited = [False] * (target_len - stamp_len + 1)

        result = []

        replaced_count = 0

        def can_replace(position: int) -> bool:
            changed = False

            for i in range(stamp_len):
                current_char = target_chars[position + i]

                if current_char == '?':
                    continue

                if current_char != stamp[i]:
                    return False

                changed = True

            return changed

        def do_replace(position: int) -> int:
            replaced = 0

            for i in range(stamp_len):
                if target_chars[position + i] != '?':
                    target_chars[position + i] = '?'
                    replaced += 1

            return replaced

        while replaced_count < target_len:
            progress = False

            for i in range(target_len - stamp_len + 1):
                if visited[i]:
                    continue

                if can_replace(i):
                    replaced = do_replace(i)

                    if replaced > 0:
                        visited[i] = True
                        progress = True
                        replaced_count += replaced
                        result.append(i)

            if not progress:
                return []

        result.reverse()
        return result

The implementation follows the reverse simulation strategy directly.

The target string is converted into a mutable list named target_chars. This allows characters to be replaced with '?'.

The can_replace() helper checks whether a stamp window can be erased safely. It ensures that every non-question-mark character matches the corresponding stamp character. It also verifies that at least one actual character would be erased.

The do_replace() helper performs the actual replacement and returns how many characters were newly erased. This count is used to track overall progress.

The main loop repeatedly scans every possible stamp position. Whenever a valid window is found, the algorithm erases it and records the index.

If an entire pass completes without any progress, then the target cannot be fully erased, meaning no valid stamping sequence exists.

Finally, the result is reversed because we recorded operations in reverse order.

Go Solution

func movesToStamp(stamp string, target string) []int {
	stampLen := len(stamp)
	targetLen := len(target)

	targetChars := []byte(target)

	visited := make([]bool, targetLen-stampLen+1)

	result := []int{}

	replacedCount := 0

	canReplace := func(position int) bool {
		changed := false

		for i := 0; i < stampLen; i++ {
			currentChar := targetChars[position+i]

			if currentChar == '?' {
				continue
			}

			if currentChar != stamp[i] {
				return false
			}

			changed = true
		}

		return changed
	}

	doReplace := func(position int) int {
		replaced := 0

		for i := 0; i < stampLen; i++ {
			if targetChars[position+i] != '?' {
				targetChars[position+i] = '?'
				replaced++
			}
		}

		return replaced
	}

	for replacedCount < targetLen {
		progress := false

		for i := 0; i <= targetLen-stampLen; i++ {
			if visited[i] {
				continue
			}

			if canReplace(i) {
				replaced := doReplace(i)

				if replaced > 0 {
					visited[i] = true
					progress = true
					replacedCount += replaced
					result = append(result, i)
				}
			}
		}

		if !progress {
			return []int{}
		}
	}

	for left, right := 0, len(result)-1; left < right; left, right = left+1, right-1 {
		result[left], result[right] = result[right], result[left]
	}

	return result
}

The Go implementation mirrors the Python logic closely.

The mutable target string is represented using a byte slice. Since Go strings are immutable, converting to []byte is necessary for in-place replacement.

The helper functions are implemented as closures. Slice operations and index handling are explicit, but otherwise the logic is identical.

Go does not distinguish between nil and empty slices in LeetCode grading for this problem, so returning []int{} is sufficient when no solution exists.

Worked Examples

Example 1

Input:

stamp = "abc"
target = "ababc"

Initial state:

Step	Current Target	Action	Result Array
0	ababc	Start	[]

Possible windows:

• Index 0 -> "aba" does not match
• Index 1 -> "bab" does not match
• Index 2 -> "abc" matches

Stamp reverse at index 2:

Step	Current Target	Action	Result Array
1	ab???	Replace index 2	[2]

Next scan:

• Index 0 -> "ab?" is compatible with "abc"

Stamp reverse at index 0:

Step	Current Target	Action	Result Array
2	?????	Replace index 0	[2, 0]

Reverse result:

[0, 2]

Example 2

Input:

stamp = "abca"
target = "aabcaca"

Initial target:

aabcaca

First valid window:

• Index 1 -> "abca"

Replace:

Step	Current Target	Result
1	a????ca	[1]

Next valid window:

• Index 3 -> "? ? ca" compatible with "abca"

Replace:

Step	Current Target	Result
2	a??????	[1, 3]

Next valid window:

• Index 0 -> "a???"

Replace:

Step	Current Target	Result
3	???????	[1, 3, 0]

Reverse:

[0, 3, 1]

Another valid answer is:

[3, 0, 1]

Both are accepted.

Complexity Analysis

Measure	Complexity	Explanation
Time	O((N - M + 1) * N * M)	Each scan checks every window and each check may inspect the full stamp
Space	O(N)	Mutable target array, visited array, and result storage

The algorithm may repeatedly scan all possible windows before the entire target becomes question marks. Each window comparison may inspect up to M characters. Since at least one new character is erased during successful operations, the number of successful replacements is bounded by N.

Test Cases

from typing import List

class Solution:
    def movesToStamp(self, stamp: str, target: str) -> List[int]:
        stamp_len = len(stamp)
        target_len = len(target)

        target_chars = list(target)

        visited = [False] * (target_len - stamp_len + 1)

        result = []

        replaced_count = 0

        def can_replace(position: int) -> bool:
            changed = False

            for i in range(stamp_len):
                current_char = target_chars[position + i]

                if current_char == '?':
                    continue

                if current_char != stamp[i]:
                    return False

                changed = True

            return changed

        def do_replace(position: int) -> int:
            replaced = 0

            for i in range(stamp_len):
                if target_chars[position + i] != '?':
                    target_chars[position + i] = '?'
                    replaced += 1

            return replaced

        while replaced_count < target_len:
            progress = False

            for i in range(target_len - stamp_len + 1):
                if visited[i]:
                    continue

                if can_replace(i):
                    replaced = do_replace(i)

                    if replaced > 0:
                        visited[i] = True
                        progress = True
                        replaced_count += replaced
                        result.append(i)

            if not progress:
                return []

        result.reverse()
        return result

solver = Solution()

assert solver.movesToStamp("abc", "ababc") != []  # basic example
assert solver.movesToStamp("abca", "aabcaca") != []  # overlapping stamps
assert solver.movesToStamp("a", "a") == [0]  # smallest valid input
assert solver.movesToStamp("abc", "abc") == [0]  # exact stamp match
assert solver.movesToStamp("ab", "abab") != []  # repeated pattern
assert solver.movesToStamp("xyz", "xyzxyz") != []  # multiple identical segments
assert solver.movesToStamp("abc", "def") == []  # impossible target
assert solver.movesToStamp("aa", "aaaa") != []  # repeated characters
assert solver.movesToStamp("abc", "aabcc") == []  # mismatched structure
assert solver.movesToStamp("ab", "bbbb") == []  # missing required characters

Test	Why
"abc", "ababc"	Verifies standard example behavior
"abca", "aabcaca"	Tests overlapping stamp usage
"a", "a"	Smallest valid input
"abc", "abc"	Exact one-step stamping
"ab", "abab"	Multiple repeated stamp applications
"xyz", "xyzxyz"	Tests repeated independent regions
"abc", "def"	Impossible target detection
"aa", "aaaa"	Repeated-character handling
"abc", "aabcc"	Partial mismatch scenario
"ab", "bbbb"	No valid construction exists

Edge Cases

One important edge case occurs when the target is exactly equal to the stamp. A naive implementation might unnecessarily continue searching for additional stamp operations. In this implementation, the first successful reverse stamp converts the entire target into question marks immediately, and the algorithm terminates correctly with a single index.

Another tricky case involves overlapping stamps. For example, in "aabcaca" with stamp "abca", some characters belong to multiple stamp applications. A forward greedy strategy can easily fail here because choosing the wrong stamp order may block future progress. The reverse greedy approach avoids this issue because it only removes windows that are already consistent with the stamp.

A third important edge case is preventing infinite loops. Suppose a window already consists entirely of question marks. Technically, it still "matches" the stamp because question marks are treated as wildcards during reverse processing. However, allowing repeated stamping on already-erased regions would cause endless looping. The implementation avoids this by requiring every reverse stamp operation to erase at least one real character.

Another subtle edge case occurs when no valid solution exists. For example, stamp = "abc" and target = "def". The algorithm eventually completes a full scan without making progress. At that point, it correctly returns an empty array instead of looping forever or returning a partial solution.