Break down a hard problem into reliable checkpoints, edge-case handling, and complexity trade-offs.
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.
stamp = "abc" and target = "abcba", then s is "?????" initially. In one turn you can:
stamp at index 0 of s to obtain "abc??",stamp at index 1 of s to obtain "?abc?", orstamp at index 2 of s to obtain "??abc".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 <= 1000stamp and target consist of lowercase English letters.Problem summary: 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.
Start with the most direct exhaustive search. That gives a correctness anchor before optimizing.
Pattern signal: Stack · Greedy
"abc" "ababc"
"abca" "aabcaca"
Source-backed implementations are provided below for direct study and interview prep.
// Accepted solution for LeetCode #936: Stamping The Sequence
class Solution {
public int[] movesToStamp(String stamp, String target) {
int m = stamp.length(), n = target.length();
int[] indeg = new int[n - m + 1];
Arrays.fill(indeg, m);
List<Integer>[] g = new List[n];
Arrays.setAll(g, i -> new ArrayList<>());
Deque<Integer> q = new ArrayDeque<>();
for (int i = 0; i < n - m + 1; ++i) {
for (int j = 0; j < m; ++j) {
if (target.charAt(i + j) == stamp.charAt(j)) {
if (--indeg[i] == 0) {
q.offer(i);
}
} else {
g[i + j].add(i);
}
}
}
List<Integer> ans = new ArrayList<>();
boolean[] vis = new boolean[n];
while (!q.isEmpty()) {
int i = q.poll();
ans.add(i);
for (int j = 0; j < m; ++j) {
if (!vis[i + j]) {
vis[i + j] = true;
for (int k : g[i + j]) {
if (--indeg[k] == 0) {
q.offer(k);
}
}
}
}
}
for (int i = 0; i < n; ++i) {
if (!vis[i]) {
return new int[0];
}
}
Collections.reverse(ans);
return ans.stream().mapToInt(Integer::intValue).toArray();
}
}
// Accepted solution for LeetCode #936: Stamping The Sequence
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
}
# Accepted solution for LeetCode #936: Stamping The Sequence
class Solution:
def movesToStamp(self, stamp: str, target: str) -> List[int]:
m, n = len(stamp), len(target)
indeg = [m] * (n - m + 1)
q = deque()
g = [[] for _ in range(n)]
for i in range(n - m + 1):
for j, c in enumerate(stamp):
if target[i + j] == c:
indeg[i] -= 1
if indeg[i] == 0:
q.append(i)
else:
g[i + j].append(i)
ans = []
vis = [False] * n
while q:
i = q.popleft()
ans.append(i)
for j in range(m):
if not vis[i + j]:
vis[i + j] = True
for k in g[i + j]:
indeg[k] -= 1
if indeg[k] == 0:
q.append(k)
return ans[::-1] if all(vis) else []
// Accepted solution for LeetCode #936: Stamping The Sequence
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()
}
}
}
// Accepted solution for LeetCode #936: Stamping The Sequence
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;
}
Use this to step through a reusable interview workflow for this problem.
For each element, scan left (or right) to find the next greater/smaller element. The inner scan can visit up to n elements per outer iteration, giving O(n²) total comparisons. No extra space needed beyond loop variables.
Each element is pushed onto the stack at most once and popped at most once, giving 2n total operations = O(n). The stack itself holds at most n elements in the worst case. The key insight: amortized O(1) per element despite the inner while-loop.
Review these before coding to avoid predictable interview regressions.
Wrong move: Pushing without popping stale elements invalidates next-greater/next-smaller logic.
Usually fails on: Indices point to blocked elements and outputs shift.
Fix: Pop while invariant is violated before pushing current element.
Wrong move: Locally optimal choices may fail globally.
Usually fails on: Counterexamples appear on crafted input orderings.
Fix: Verify with exchange argument or monotonic objective before committing.