Skip to main content
Talentd

Stamping The Sequence - Solution & Explanation

HardStringStackGreedyQueue28 min readAsked at: Morgan Stanley
Practice this problem

Problem Statement

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.

  • For example, if stamp = "abc" and target = "abcba", then s is "?????" initially. In one turn you can:
    • place stamp at index 0 of s to obtain "abc??",
    • place stamp at index 1 of s to obtain "?abc?", or
    • place stamp at index 2 of s to obtain "??abc".
    Note that 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 <= 1000
  • stamp and target consist of lowercase English letters.

Approach Overview

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 1: Greedy Approach

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.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

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.

Try this approach in the editor →

Approach 2: Reverse Thinking + Topological Sorting

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:

  • In-degree array 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.
  • Adjacency list 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.
  • Queue q, used to store the numbers of all windows with an in-degree of 0.
  • Array vis, used to mark whether each position of the target string target has been covered.
  • Array 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.

Code

PythonJavaC++GoTypeScriptRust

Python

Java

C++

Go

TypeScript

Rust

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
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—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Brute Force SimulationO((n-m)*m*n)O(n)Useful for understanding the stamping process or very small inputs
Greedy Reverse Stamping with QueueO(n*m)O(n)Optimal solution for interviews and competitive programming

Video Solution

Stamping The Sequence | Live Coding with Explanation | Leetcode - 936 • Algorithms Made Easy • 7,341 views views

Watch 9 more video solutions →

Frequently Asked Questions

Is Stamping The Sequence easy or hard?
Stamping The Sequence is classified as a Hard problem because the straightforward simulation is inefficient and the optimal solution requires reversing the process and managing window dependencies. Understanding why the greedy reverse strategy works is the main challenge.
Stamping The Sequence Python/Java solution
Most implementations follow the same greedy reverse algorithm across languages. Maintain window dependency lists, push valid windows into a queue, and convert characters to question marks while recording indices. The final answer list is reversed to produce the stamping order. This logic translates directly to Python, Java, C++, and JavaScript.
How to solve Stamping The Sequence in O(n*m)?
Use a reverse greedy strategy. Track all windows of size m and record which characters match the stamp and which still need to be removed. When a window fully matches, replace its characters with question marks and update neighboring windows through a queue. Each character removal can unlock additional windows, eventually clearing the entire string.
What is the best approach for Stamping The Sequence?
The greedy reverse stamping approach is the most efficient. Instead of constructing the target from question marks, the algorithm works backward by converting valid stamp windows into question marks. A queue tracks windows that become valid after characters are removed. This reduces repeated scans and achieves O(n*m) time complexity.
Is Stamping The Sequence asked at Google/Amazon/Meta?
Stamping The Sequence is a classic hard string and greedy problem similar to questions asked at companies like Google, Amazon, and Meta. It tests problem transformation, dependency tracking, and queue-based propagation, which are common interview themes in senior-level coding rounds.
What data structure is used in Stamping The Sequence?
The optimal solution primarily uses a queue to process windows that become stampable during the reverse simulation. Additional arrays track visited windows and character dependencies. The algorithm operates on the string using greedy logic and window checks.
What is the time complexity of Stamping The Sequence?
The optimized greedy solution runs in O(n*m) time where n is the length of the target and m is the length of the stamp. Each window is processed a limited number of times while dependencies are updated through a queue. Space complexity is O(n) for tracking visited windows and removed characters.

Ready to solve this problem?

Practice Stamping The Sequence with our built-in code editor and test cases.

Practice on FleetCode
Previous

Longest Substring Without Repeating Characters

Next

Longest Palindromic Substring