Stamping The Sequence
HardUpdated: Jul 26, 2025
Practice on:
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"andtarget = "abcba", thensis"?????"initially. In one turn you can:- place
stampat index0ofsto obtain"abc??", - place
stampat index1ofsto obtain"?abc?", or - place
stampat index2ofsto obtain"??abc". Note thatstampmust be fully contained in the boundaries ofsin order to stamp (i.e., you cannot placestampat index3ofs).
- place
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.
Examples
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 <= 1000stampandtargetconsist of lowercase English letters.
Solution
Method 1 – Greedy Reverse Simulation
Intuition
Instead of building the target from all '?', we reverse the process: start from the target and repeatedly "unstamp" it by replacing stamp substrings with '?'. This way, we can greedily find the last stamp positions and work backwards, ensuring we do not exceed the allowed number of moves.
Approach
- Convert target to a list of characters.
- While there are still non-'?' characters:
- For each possible position, check if stamp can be "unstamped" (i.e., matches with '?' allowed).
- If possible, replace those characters with '?', record the position, and mark progress.
- If no progress is made in a full pass, return an empty array.
- Return the recorded positions in reverse order.
Code
C++
class Solution {
public:
vector<int> movesToStamp(string stamp, string target) {
int n = target.size(), m = stamp.size();
vector<int> ans;
bool changed = true;
vector<char> t(target.begin(), target.end());
while (changed) {
changed = false;
for (int i = 0; i <= n - m; ++i) {
bool can = false;
for (int j = 0; j < m; ++j) {
if (t[i+j] != '?' && t[i+j] != stamp[j]) break;
if (stamp[j] == t[i+j]) can = true;
if (j == m-1) {
if (can) {
for (int k = 0; k < m; ++k) t[i+k] = '?';
ans.push_back(i);
changed = true;
}
}
}
}
}
for (char c : t) if (c != '?') return {};
reverse(ans.begin(), ans.end());
return ans;
}
};
Go
func movesToStamp(stamp, target string) []int {
n, m := len(target), len(stamp)
t := []byte(target)
var ans []int
changed := true
for changed {
changed = false
for i := 0; i <= n-m; i++ {
can := false
for j := 0; j < m; j++ {
if t[i+j] != '?' && t[i+j] != stamp[j] {
can = false
break
}
if stamp[j] == t[i+j] {
can = true
}
}
if can {
for k := 0; k < m; k++ {
t[i+k] = '?'
}
ans = append(ans, i)
changed = true
}
}
}
for _, c := range t {
if c != '?' {
return []int{}
}
}
// reverse ans
for i, j := 0, len(ans)-1; i < j; i, j = i+1, j-1 {
ans[i], ans[j] = ans[j], ans[i]
}
return ans
}
Java
class Solution {
public int[] movesToStamp(String stamp, String target) {
int n = target.length(), m = stamp.length();
char[] t = target.toCharArray();
List<Integer> ans = new ArrayList<>();
boolean changed = true;
while (changed) {
changed = false;
for (int i = 0; i <= n - m; ++i) {
boolean can = false;
for (int j = 0; j < m; ++j) {
if (t[i+j] != '?' && t[i+j] != stamp.charAt(j)) break;
if (stamp.charAt(j) == t[i+j]) can = true;
if (j == m-1) {
if (can) {
for (int k = 0; k < m; ++k) t[i+k] = '?';
ans.add(i);
changed = true;
}
}
}
}
}
for (char c : t) if (c != '?') return new int[0];
Collections.reverse(ans);
return ans.stream().mapToInt(i->i).toArray();
}
}
Kotlin
class Solution {
fun movesToStamp(stamp: String, target: String): IntArray {
val n = target.length
val m = stamp.length
val t = target.toCharArray()
val ans = mutableListOf<Int>()
var changed = true
while (changed) {
changed = false
for (i in 0..n-m) {
var can = false
for (j in 0 until m) {
if (t[i+j] != '?' && t[i+j] != stamp[j]) break
if (stamp[j] == t[i+j]) can = true
if (j == m-1) {
if (can) {
for (k in 0 until m) t[i+k] = '?'
ans.add(i)
changed = true
}
}
}
}
}
if (t.any { it != '?' }) return intArrayOf()
return ans.reversed().toIntArray()
}
}
Python
def movesToStamp(stamp: str, target: str) -> list[int]:
n, m = len(target), len(stamp)
t = list(target)
ans = []
changed = True
while changed:
changed = False
for i in range(n-m+1):
can = False
for j in range(m):
if t[i+j] != '?' and t[i+j] != stamp[j]:
break
if stamp[j] == t[i+j]:
can = True
if j == m-1:
if can:
for k in range(m):
t[i+k] = '?'
ans.append(i)
changed = True
if any(c != '?' for c in t):
return []
return ans[::-1]
Rust
impl Solution {
pub fn moves_to_stamp(stamp: String, target: String) -> Vec<i32> {
let n = target.len();
let m = stamp.len();
let mut t: Vec<char> = target.chars().collect();
let mut ans = Vec::new();
let mut changed = true;
while changed {
changed = false;
for i in 0..=n-m {
let mut can = false;
for j in 0..m {
if t[i+j] != '?' && t[i+j] != stamp.chars().nth(j).unwrap() { break; }
if stamp.chars().nth(j).unwrap() == t[i+j] { can = true; }
if j == m-1 {
if can {
for k in 0..m { t[i+k] = '?'; }
ans.push(i as i32);
changed = true;
}
}
}
}
}
if t.iter().any(|&c| c != '?') { return vec![]; }
ans.reverse();
ans
}
}
TypeScript
class Solution {
movesToStamp(stamp: string, target: string): number[] {
const n = target.length, m = stamp.length;
const t = target.split('');
const ans: number[] = [];
let changed = true;
while (changed) {
changed = false;
for (let i = 0; i <= n - m; ++i) {
let can = false;
for (let j = 0; j < m; ++j) {
if (t[i+j] !== '?' && t[i+j] !== stamp[j]) break;
if (stamp[j] === t[i+j]) can = true;
if (j === m-1) {
if (can) {
for (let k = 0; k < m; ++k) t[i+k] = '?';
ans.push(i);
changed = true;
}
}
}
}
}
if (t.some(c => c !== '?')) return [];
return ans.reverse();
}
}
Complexity
- ⏰ Time complexity:
O((N-M)*M*N)– Each pass may scan the whole string, and up to 10*N passes. - 🧺 Space complexity:
O(N)– For the answer and working string.