Stamping The Sequence
Problem
Given strings stamp and target, return a sequence of stamping positions that produces target from an all-'?' string. Return [] if impossible.
stamp = "abc", target = "ababc"[0,2]def movesToStamp(stamp, target):
t = list(target)
s = list(stamp)
moves = []
placed = True
total_changed = 0
star = ['?'] * len(t)
while placed:
placed = False
for i in range(len(t) - len(s) + 1):
changed = 0
valid = False
for j in range(len(s)):
if t[i + j] == '?': continue
if t[i + j] != s[j]: changed = -1; break
valid = True
changed += 1
if changed > 0 and valid:
for j in range(len(s)): t[i + j] = '?'
moves.append(i)
placed = True
total_changed += changed
if total_changed == len(target): return moves[::-1]
return [] if any(c != '?' for c in t) else moves[::-1]function movesToStamp(stamp, target) {
const t = target.split(''), s = stamp.split('');
const moves = [];
let placed = true, total = 0;
while (placed) {
placed = false;
for (let i = 0; i <= t.length - s.length; i++) {
let changed = 0, valid = false;
for (let j = 0; j < s.length; j++) {
if (t[i + j] === '?') continue;
if (t[i + j] !== s[j]) { changed = -1; break; }
valid = true; changed++;
}
if (changed > 0 && valid) {
for (let j = 0; j < s.length; j++) t[i + j] = '?';
moves.push(i); placed = true; total += changed;
if (total === target.length) return moves.reverse();
}
}
}
return t.some(c => c !== '?') ? [] : moves.reverse();
}class Solution {
public int[] movesToStamp(String stamp, String target) {
char[] t = target.toCharArray(), s = stamp.toCharArray();
List<Integer> moves = new ArrayList<>();
boolean placed = true; int total = 0;
while (placed) {
placed = false;
for (int i = 0; i <= t.length - s.length; i++) {
int changed = 0; boolean valid = false;
for (int j = 0; j < s.length; j++) {
if (t[i + j] == '?') continue;
if (t[i + j] != s[j]) { changed = -1; break; }
valid = true; changed++;
}
if (changed > 0 && valid) {
for (int j = 0; j < s.length; j++) t[i + j] = '?';
moves.add(i); placed = true; total += changed;
}
}
}
for (char c : t) if (c != '?') return new int[0];
int[] out = new int[moves.size()];
for (int i = 0; i < out.length; i++) out[i] = moves.get(moves.size() - 1 - i);
return out;
}
}vector<int> movesToStamp(string stamp, string target) {
string t = target, s = stamp;
vector<int> moves;
bool placed = true; int total = 0;
while (placed) {
placed = false;
for (int i = 0; i + (int)s.size() <= (int)t.size(); i++) {
int changed = 0; bool valid = false;
for (int j = 0; j < (int)s.size(); j++) {
if (t[i + j] == '?') continue;
if (t[i + j] != s[j]) { changed = -1; break; }
valid = true; changed++;
}
if (changed > 0 && valid) {
for (int j = 0; j < (int)s.size(); j++) t[i + j] = '?';
moves.push_back(i); placed = true; total += changed;
}
}
}
for (char c : t) if (c != '?') return {};
reverse(moves.begin(), moves.end());
return moves;
}Explanation
The clever idea is to solve this backwards. Instead of stamping onto blanks to build the target, we start from the finished target and "un-stamp" it back into all ?, recording each removal.
We look for any window where the stamp matches the current target — but a position counts as matching if it already equals the stamp's letter or is already a ? (a spot a later stamp would have covered). When we find such a window with at least one real letter, we erase it to ? and record that index in moves.
We keep sweeping the string, erasing windows, until a full pass makes no change (placed stays false). We also track total_changed; once every real character has been turned into ?, we know the whole target was built.
Because we removed stamps in reverse, the recorded order is the un-stamping order. To play it forward we return moves[::-1]. If any non-? remains stuck, it was impossible, so we return [].
Example: stamp = "abc", target = "ababc". We can un-stamp the window at index 2 (abc) first, then index 0. Reversing gives the forward sequence [0, 2].