936. Stamping The Sequence - Solution

Q: 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.

Q: 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.

Q: 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.

Q: 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.

Q: 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.

Q: 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.

Q: 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.

The problem

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.

Python

from typing import List

class Solution:
    def movesToStamp(self, stamp: str, target: str) -> List[int]:
        m, n = len(stamp), len(target)
        target = list(target)
        visited = [False] * n
        res = []
        stars = 0

        def canStamp(pos: int) -> bool:
            for i in range(m):
                if target[i + pos] != '?' and target[i + pos] != stamp[i]:
                    return False
            return True

        def replaceWithStar(pos: int) -> int:
            count = 0
            for i in range(m):
                if target[i + pos] != '?':
                    target[i + pos] = '?'
                    count += 1
            return count

        while stars < n:
            stamped = False
            for i in range(n - m + 1):
                if not visited[i] and canStamp(i):
                    stars += replaceWithStar(i)
                    stamped = True
                    visited[i] = True
                    res.append(i)
                    if stars == n:
                        break
            if not stamped:
                return []

        return res[::-1]

# Example usage
sol = Solution()
result = sol.movesToStamp("abc", "ababc")
print(result)

Java

import java.util.*;

class Solution {
    public int[] movesToStamp(String stamp, String target) {
        int m = stamp.length();
        int n = target.length();
        char[] targetArr = target.toCharArray();
        boolean[] visited = new boolean[n];
        List<Integer> res = new ArrayList<>();
        int stars = 0;

        while (stars < n) {
            boolean stamped = false;
            for (int i = 0; i <= n - m; i++) {
                if (!visited[i] && canStamp(targetArr, stamp.toCharArray(), i)) {
                    stars += replaceWithStar(targetArr, i, m);
                    stamped = true;
                    visited[i] = true;
                    res.add(i);
                    if (stars == n) break;
                }
            }
            if (!stamped) return new int[0];
        }

        int[] resultArr = new int[res.size()];
        for (int i = 0; i < res.size(); i++) {
            resultArr[i] = res.get(res.size() - 1 - i);
        }
        return resultArr;
    }

    private boolean canStamp(char[] target, char[] stamp, int pos) {
        for (int i = 0; i < stamp.length; ++i) {
            if (target[i + pos] != '?' && target[i + pos] != stamp[i])
                return false;
        }
        return true;
    }

    private int replaceWithStar(char[] target, int pos, int len) {
        int count = 0;
        for (int i = 0; i < len; ++i) {
            if (target[i + pos] != '?') {
                target[i + pos] = '?';
                count++;
            }
        }
        return count;
    }

    // Example usage
    public static void main(String[] args) {
        Solution sol = new Solution();
        int[] result = sol.movesToStamp("abc", "ababc");
        System.out.println(Arrays.toString(result));
    }
}

C++

#include <vector>
#include <string>
using namespace std;

class Solution {
public:
    vector<int> movesToStamp(string stamp, string target) {
        int m = stamp.size(), n = target.size();
        vector<int> res;
        vector<bool> visited(n, false);
        int stars = 0;

        while (stars < n) {
            bool stamped = false;
            for (int i = 0; i <= n - m; ++i) {
                if (!visited[i] && canStamp(target, stamp, i)) {
                    stars += replaceWithStar(target, i, m);
                    stamped = true;
                    visited[i] = true;
                    res.push_back(i);
                    if (stars == n) break;
                }
            }
            if (!stamped) return {};
        }

        reverse(res.begin(), res.end());
        return res;
    }

    bool canStamp(string &target, string &stamp, int pos) {
        for (int i = 0; i < stamp.size(); ++i) {
            if (target[i + pos] != '?' && target[i + pos] != stamp[i]) return false;
        }
        return true;
    }

    int replaceWithStar(string &target, int pos, int len) {
        int count = 0;
        for (int i = 0; i < len; ++i) {
            if (target[i + pos] != '?') {
                target[i + pos] = '?';
                count++;
            }
        }
        return count;
    }
};

// Example usage
int main() {
    Solution sol;
    vector<int> result = sol.movesToStamp("abc", "ababc");
    for (int index : result) {
        printf("%d ", index);
    }
    printf("\n");
    return 0;
}

JavaScript

function movesToStamp(stamp, target) {
    const m = stamp.length, n = target.length;
    const targetArr = target.split('');
    const visited = Array(n).fill(false);
    const res = [];
    let stars = 0;

    const canStamp = (pos) => {
        for (let i = 0; i < m; i++) {
            if (targetArr[i + pos] !== '?' && targetArr[i + pos] !== stamp[i])
                return false;
        }
        return true;
    };

    const replaceWithStar = (pos) => {
        let count = 0;
        for (let i = 0; i < m; i++) {
            if (targetArr[i + pos] !== '?') {
                targetArr[i + pos] = '?';
                count++;
            }
        }
        return count;
    };

    while (stars < n) {
        let stamped = false;
        for (let i = 0; i <= n - m; i++) {
            if (!visited[i] && canStamp(i)) {
                stars += replaceWithStar(i);
                stamped = true;
                visited[i] = true;
                res.push(i);
                if (stars === n) break;
            }
        }
        if (!stamped) return [];
    }

    return res.reverse();
}

// Example usage
const result = movesToStamp("abc", "ababc");
console.log(result);

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <stdbool.h>

#define MAX_TURNS 10000

bool canStamp(char *target, char *stamp, int pos) {
    for (int i = 0; i < strlen(stamp); i++) {
        if (target[pos + i] != '?' && target[pos + i] != stamp[i]) {
            return false;
        }
    }
    return true;
}

int doStamp(char *target, char *stamp, int pos) {
    int stamped = 0;
    for (int i = 0; i < strlen(stamp); i++) {
        if (target[pos + i] != '?') {
            target[pos + i] = '?';
            stamped++;
        }
    }
    return stamped;
}

int *movesToStamp(char *stamp, char *target, int *returnSize) {
    int stampLen = strlen(stamp);
    int targetLen = strlen(target);
    int *res = (int *)malloc(sizeof(int) * MAX_TURNS);
    *returnSize = 0;
    int stamped;  
    int totalStamped = 0;    
    bool stampedSomething;

    do {
        stampedSomething = false;
        for (int i = 0; i <= targetLen - stampLen; i++) {
            if (canStamp(target, stamp, i)) {
                stamped = doStamp(target, stamp, i);
                if (stamped > 0) {
                    res[(*returnSize)++] = i;
                    stampedSomething = true;
                    totalStamped += stamped;
                    if (totalStamped == targetLen) {
                        break;
                    }
                }
            }
        }
    } while (stampedSomething && totalStamped < targetLen);

    if (totalStamped < targetLen) {
        *returnSize = 0;
        free(res);
        return NULL;
    }

    for (int i = 0; i < *returnSize / 2; ++i) {
        int temp = res[i];
        res[i] = res[*returnSize - i - 1];
        res[*returnSize - i - 1] = temp;
    }

    return res;
}

int main() {
    int returnSize;
    char stamp[] = "abc";
    char target[] = "ababc";
    int* result = movesToStamp(stamp, target, &returnSize);
    printf("[");
    for (int i = 0; i < returnSize; i++) {
        printf("%d%s", result[i], (i == returnSize - 1) ? "" : ", ");
    }
    printf("]\n");
    free(result);
    return 0;
}

using System;
using System.Collections.Generic;

public class Solution {
    public int[] MovesToStamp(string stamp, string target) {
        int m = stamp.Length, n = target.Length;
        char[] targetArr = target.ToCharArray();
        bool[] visited = new bool[n];
        List<int> res = new List<int>();
        int stars = 0;

        while (stars < n) {
            bool stamped = false;
            for (int i = 0; i <= n - m; i++) {
                if (!visited[i] && CanStamp(targetArr, stamp.ToCharArray(), i)) {
                    stars += ReplaceWithStar(targetArr, i, m);
                    stamped = true;
                    visited[i] = true;
                    res.Add(i);
                    if (stars == n) break;
                }
            }
            if (!stamped) return new int[0];
        }

        res.Reverse();
        return res.ToArray();
    }

    private bool CanStamp(char[] target, char[] stamp, int pos) {
        for (int i = 0; i < stamp.Length; i++) {
            if (target[i + pos] != '?' && target[i + pos] != stamp[i])
                return false;
        }
        return true;
    }

    private int ReplaceWithStar(char[] target, int pos, int length) {
        int count = 0;
        for (int i = 0; i < length; i++) {
            if (target[i + pos] != '?') {
                target[i + pos] = '?';
                count++;
            }
        }
        return count;
    }

    // Example usage
    public static void Main(string[] args) {
        Solution sol = new Solution();
        int[] result = sol.MovesToStamp("abc", "ababc");
        Console.WriteLine(String.Join(", ", result));
    }
}

The Python implementation uses a list to track the positions that can potentially be converted to '?' by successful stamping. It iterates over possible positions, replaces segments matching the stamp criteria, and then checks if the entire target can become '?'. It appends successfully stamped indices to a list that represents the reverse path of stamping.

Complexity

Time Complexity: O((N-M+1)*M) akin to other implementations as we check each valid stamping position.

Space Complexity: O(N) necessary for maintaining resulting indices and tracking visitations.

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.

TypeScript

function movesToStamp(stamp: string, target: string): number[] {
    const m: number = stamp.length;
    const n: number = target.length;
    const indeg: number[] = Array(n - m + 1).fill(m);
    const g: number[][] = Array.from({ length: n }, () => []);
    const q: number[] = [];
    for (let i = 0; i < n - m + 1; ++i) {
        for (let j = 0; j < m; ++j) {
            if (target[i + j] === stamp[j]) {
                if (--indeg[i] === 0) {
                    q.push(i);
                }
            } else {
                g[i + j].push(i);
            }
        }
    }

    const ans: number[] = [];
    const vis: boolean[] = Array(n).fill(false);
    while (q.length) {
        const i: number = q.shift()!;
        ans.push(i);
        for (let j = 0; j < m; ++j) {
            if (!vis[i + j]) {
                vis[i + j] = true;
                for (const k of g[i + j]) {
                    if (--indeg[k] === 0) {
                        q.push(k);
                    }
                }
            }
        }
    }
    if (!vis.every(v => v)) {
        return [];
    }
    ans.reverse();
    return ans;
}

func movesToStamp(stamp string, target string) (ans []int) {
	m, n := len(stamp), len(target)
	indeg := make([]int, n-m+1)
	for i := range indeg {
		indeg[i] = m
	}
	g := make([][]int, n)
	q := []int{}
	for i := 0; i < n-m+1; i++ {
		for j := range stamp {
			if target[i+j] == stamp[j] {
				indeg[i]--
				if indeg[i] == 0 {
					q = append(q, i)
				}
			} else {
				g[i+j] = append(g[i+j], i)
			}
		}
	}
	vis := make([]bool, n)
	for len(q) > 0 {
		i := q[0]
		q = q[1:]
		ans = append(ans, i)
		for j := range stamp {
			if !vis[i+j] {
				vis[i+j] = true
				for _, k := range g[i+j] {
					indeg[k]--
					if indeg[k] == 0 {
						q = append(q, k)
					}
				}
			}
		}
	}
	for _, v := range vis {
		if !v {
			return []int{}
		}
	}
	for i, j := 0, len(ans)-1; i < j; i, j = i+1, j-1 {
		ans[i], ans[j] = ans[j], ans[i]
	}
	return
}

Rust

use std::collections::VecDeque;

impl Solution {
    pub fn moves_to_stamp(stamp: String, target: String) -> Vec<i32> {
        let m = stamp.len();
        let n = target.len();

        let mut indeg: Vec<usize> = vec![m; n - m + 1];
        let mut g: Vec<Vec<usize>> = vec![Vec::new(); n];
        let mut q: VecDeque<usize> = VecDeque::new();

        for i in 0..n - m + 1 {
            for j in 0..m {
                if target.chars().nth(i + j).unwrap() == stamp.chars().nth(j).unwrap() {
                    indeg[i] -= 1;
                    if indeg[i] == 0 {
                        q.push_back(i);
                    }
                } else {
                    g[i + j].push(i);
                }
            }
        }

        let mut ans: Vec<i32> = Vec::new();
        let mut vis: Vec<bool> = vec![false; n];

        while let Some(i) = q.pop_front() {
            ans.push(i as i32);

            for j in 0..m {
                if !vis[i + j] {
                    vis[i + j] = true;

                    for &k in g[i + j].iter() {
                        indeg[k] -= 1;
                        if indeg[k] == 0 {
                            q.push_back(k);
                        }
                    }
                }
            }
        }

        if vis.iter().all(|&v| v) {
            ans.reverse();
            ans
        } else {
            Vec::new()
        }
    }
}

Try this approach in the editor

Complexity comparison

Approach	Complexity
Greedy Approach	Time Complexity: O((N-M+1)M) akin to other implementations as we check each valid stamping position. Space Complexity:* O(N) necessary for maintaining resulting indices and tracking visitations.
Reverse Thinking + Topological Sorting	–

Approach

Complexity

Greedy Approach

Time Complexity: O((N-M+1)*M) akin to other implementations as we check each valid stamping position.

Space Complexity: O(N) necessary for maintaining resulting indices and tracking visitations.

Reverse Thinking + Topological Sorting

–

Complexity analysis

Approach	Time	Space	When to Use
Brute Force Simulation	O((n-m)mn)	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

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.

Stamping The Sequence solution and explanation

The problem

Approach overview

Approach 1: Greedy Approach

Approach 2: Reverse Thinking + Topological Sorting

Complexity comparison

Complexity analysis

Frequently asked questions

Comments

Stamping The Sequence solution and explanation

The problem

Approach overview

Approach 1: Greedy Approach

Approach 2: Reverse Thinking + Topological Sorting

Complexity comparison

Complexity analysis

Frequently asked questions

Comments

Related problems