Watch 10 video solutions for Stamping The Sequence, a hard level problem involving String, Stack, Greedy. This walkthrough by Algorithms Made Easy has 7,246 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
You are given two strings stamp and target. Initially, there is a string s of length target.length with all s[i] == '?'.
In one turn, you can place stamp over s and replace every letter in the s with the corresponding letter from stamp.
stamp = "abc" and target = "abcba", then s is "?????" initially. In one turn you can:
stamp at index 0 of s to obtain "abc??",stamp at index 1 of s to obtain "?abc?", orstamp at index 2 of s to obtain "??abc".stamp must be fully contained in the boundaries of s in order to stamp (i.e., you cannot place stamp at index 3 of s).We want to convert s to target using at most 10 * target.length turns.
Return an array of the index of the left-most letter being stamped at each turn. If we cannot obtain target from s within 10 * target.length turns, return an empty array.
Example 1:
Input: stamp = "abc", target = "ababc" Output: [0,2] Explanation: Initially s = "?????". - Place stamp at index 0 to get "abc??". - Place stamp at index 2 to get "ababc". [1,0,2] would also be accepted as an answer, as well as some other answers.
Example 2:
Input: stamp = "abca", target = "aabcaca" Output: [3,0,1] Explanation: Initially s = "???????". - Place stamp at index 3 to get "???abca". - Place stamp at index 0 to get "abcabca". - Place stamp at index 1 to get "aabcaca".
Constraints:
1 <= stamp.length <= target.length <= 1000stamp and target consist of lowercase English letters.Problem Overview: You are given a stamp string and a target string. The goal is to reconstruct how the target could be formed by repeatedly placing the stamp over a sequence of question marks. Each stamp operation overwrites matching characters. The task is to return the sequence of stamping positions that produces the target.
Approach 1: Brute Force Simulation (O((n-m)*m*n) time, O(n) space)
The direct idea is to repeatedly scan the target string and try stamping at every possible position. For each window of size m, check if the stamp matches the current characters or question marks. If it matches, replace the window with question marks and record the index. Continue scanning until the entire string becomes question marks. This method uses heavy repeated comparisons and may re-check many windows, which makes it inefficient for large inputs.
Approach 2: Greedy Reverse Stamping with Queue (O(n*m) time, O(n) space)
The optimal strategy works in reverse. Instead of building the target from question marks, start from the target and try to "unstamp" it. For every window of length m, track which characters already match the stamp and which still need to be removed. If a window fully matches the stamp, it can be replaced with question marks immediately. When a window becomes valid to remove, push its index into a queue.
Process windows from the queue and mark their characters as removed. Every time a character becomes a question mark, update neighboring windows that depend on it. Once all required characters of a window match, enqueue it. This greedy propagation avoids rescanning the entire string repeatedly and guarantees each character is processed only a limited number of times.
The algorithm relies on efficient window tracking and dependency updates using a queue. Conceptually it combines greedy reasoning with window checks over the string. The result list is built during the reverse process and finally reversed to produce the correct stamping order.
Recommended for interviews: The greedy reverse stamping approach is the expected solution. It demonstrates the ability to flip the problem perspective and use queue-driven propagation to avoid repeated scans. A brute force simulation shows understanding of the mechanics, but the greedy approach proves you can optimize complex string transformations.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force Simulation | O((n-m)*m*n) | O(n) | Useful for understanding the stamping process or very small inputs |
| Greedy Reverse Stamping with Queue | O(n*m) | O(n) | Optimal solution for interviews and competitive programming |