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.

Examples

Example 1

1
2
3
4
5
6

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

1
2
3
4
5
6

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.

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

  1. Convert target to a list of characters.
  2. 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.
  3. Return the recorded positions in reverse order.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

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;
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38

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
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

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();
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

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()
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

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]
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

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
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

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.