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.
This approach involves reversing the stamping process. Instead of trying to form the target from '?' gradually, we attempt to convert the target into '?' by 'un-stamping' in a greedy way.
We can try and 'stamp out' the pattern from the target where it matches. This continues until we've stamped out the entire target or until we determine it's impossible to do so within the given constraints.
This solution works by simulating the stamping as a process of replacing portions of the target string with '?'. This approach checks all possible positions to stamp and only performs stamping if the stamp can fully 'cover' or 'match' the target at the current position without introducing 'new' unmatched characters. The process continues until the whole target is replaced with '?'.
Each time we successfully stamp a portion, we accumulate that index in our results and later reverse the results to match the sequence from initial stamping to the final target.
Time Complexity: O((N-M+1)*M) where N is the length of target and M is the length of stamp. We effectively iterate through the length of the target and for each possible stamping position, we may iterate through the stamp.
Space Complexity: O(N) to hold the result of the stampping sequence.
If we operate on the sequence in a forward manner, it would be quite complicated because subsequent operations would overwrite previous ones. Therefore, we consider operating on the sequence in a reverse manner, i.e., starting from the target string target and considering the process of turning target into ?????.
Let's denote the length of the stamp as m and the length of the target string as n. If we operate on the target string with the stamp, there are n-m+1 starting positions where the stamp can be placed. We can enumerate these n-m+1 starting positions and use a method similar to topological sorting to operate in reverse.
Firstly, we clarify that each starting position corresponds to a window of length m.
Next, we define the following data structures or variables:
indeg, where indeg[i] represents how many characters in the i-th window are different from the characters in the stamp. Initially, indeg[i]=m. If indeg[i]=0, it means that all characters in the i-th window are the same as those in the stamp, and we can place the stamp in the i-th window.g, where g[i] represents the set of all windows with different characters from the stamp on the i-th position of the target string target.q, used to store the numbers of all windows with an in-degree of 0.vis, used to mark whether each position of the target string target has been covered.ans, used to store the answer.Then, we perform topological sorting. In each step of the topological sorting, we take out the window number i at the head of the queue, and put i into the answer array ans. Then, we enumerate each position j in the stamp. If the j-th position in the i-th window has not been covered, we cover it and reduce the in-degree of all windows in the indeg array that are the same as the j-th position in the i-th window by 1. If the in-degree of a window becomes 0, we put it into the queue q for processing next time.
After the topological sorting is over, if every position of the target string target has been covered, then the answer array ans stores the answer we are looking for. Otherwise, the target string target cannot be covered, and we return an empty array.
The time complexity is O(n times (n - m + 1)), and the space complexity is O(n times (n - m + 1)). Here, n and m are the lengths of the target string target and the stamp, respectively.
| Approach | Complexity |
|---|---|
| Greedy Approach | Time Complexity: O((N-M+1)*M) where N is the length of target and M is the length of stamp. We effectively iterate through the length of the target and for each possible stamping position, we may iterate through the stamp. Space Complexity: O(N) to hold the result of the stampping sequence. |
| Reverse Thinking + Topological Sorting | — |
| 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 |
Stamping The Sequence | Live Coding with Explanation | Leetcode - 936 • Algorithms Made Easy • 7,246 views views
Watch 9 more video solutions →Practice Stamping The Sequence with our built-in code editor and test cases.
Practice on FleetCode