Skip to main content
CodePeet

Stamping The Sequence

Try it yourself
HardProblemExternal link

Description

You are given two strings, stamp (length m) and target (length n). Start with a string s of n question marks, "??…?".

In one turn, choose a position i with 0 ≤ i ≤ n − m and press the stamp there. The letters s[i] to s[i+m−1] are replaced by the stamp's letters. The stamp must fit completely inside s. A later stamp overwrites whatever an earlier one left where they overlap.

Turn s into target using at most 10 × n turns. Return the list of positions you pressed, in order. If it cannot be done, return an empty list [].

A few details matter:

  • Any valid list is accepted. Often several orders work.
  • Every position must end up covered by some stamp. A ? can never stay in the final string.
  • The same position may be stamped more than once, and stamps may overlap.

Examples

Example 1

Input: stamp = "cat", target = "ccatt"

Output: [0, 2, 1] (other orders such as [2, 0, 1] are also accepted)

Explanation: Starting from "?????":

  • stamp at 0 → "cat??"
  • stamp at 2 → "cacat" (overwrites the t at position 2)
  • stamp at 1 → "ccatt" (overwrites positions 1 to 3)

The last stamp, at 1, is the one fully visible in the target: "ccatt".

Example 2

Input: stamp = "ab", target = "aba"

Output: []

Explanation: The last position can only ever be written by a stamp that ends there, which is the stamp at position 1, and that always writes "b". So no order of stamps can finish with "a".

Example 3

Input: stamp = "aba", target = "ababa"

Output: [0, 2] (or [2, 0])

Explanation: Stamp at 0 → "aba??", then at 2 → "ababa". The two stamps overlap at position 2, where both write "a", so either order works.

Constraints

  • 1 ≤ stamp.length ≤ target.length ≤ 1000
  • stamp and target consist of lowercase English letters.

Editorial

Brute Force

Intuition

The most direct idea is to simulate stamping forwards and try everything. Start from the all-? string. From any string, pressing the stamp at each of the n − m + 1 positions gives up to n − m + 1 new strings. Explore them with a breadth-first search: a queue of strings to try, and a map from each string reached to the list of stamps that made it.

  • If the target comes out of the queue, return its list of stamps. Breadth-first search reaches every string by its shortest list of stamps, and we will see later that any reachable target needs at most n − m + 1 stamps, far under the 10 × n limit.
  • If the queue runs dry, every string stamping could ever make has been tried, so the target is impossible. Return [].

The search always ends, because every position holds either ? or one of the stamp's letters, so there are only finitely many strings.

Step-by-Step Explanation

We trace Example 2, stamp = "ab", target = "aba". The row shows the queue of strings; the list underneath holds the strings already expanded.

Step 1: Start the queue with "???".

Step 2: Take "???" off the front: not the target.

Step 3: Stamping "???" at 0 gives "ab?", which is new — add it to the queue.

Step 4: Stamping "???" at 1 gives "?ab", which is new — add it to the queue.

Step 5: Take "ab?" off the front: not the target.

Step 6: Stamping "ab?" at 1 gives "aab", which is new — add it to the queue.

Step 7: Take "?ab" off the front: not the target.

Step 8: Stamping "?ab" at 0 gives "abb", which is new — add it to the queue.

Step 9: Take "aab" off the front: not the target. Stamping at 0 gives "abb", at 1 gives "aab" — all seen already.

Step 10: Take "abb" off the front: not the target. Stamping at 0 gives "abb", at 1 gives "aab" — all seen already.

Step 11: The queue is empty: only 5 strings can ever be made, and "aba" is not among them. Return [].

Brute Force — Stamping Forwards Until Nothing New Appears — Every string the stamp can make, explored breadth-first; the row underneath lists the strings already expanded.

Algorithm

  1. Put "?" × n in a queue, and record that it needs no stamps.
  2. While the queue is not empty:
    • Take the front string s. If s == target, return its list of stamps.
    • For each i from 0 to n − m, let t = s with the stamp pressed at i. If t has not been seen, record t's list as s's list plus i, and add t to the queue.
  3. Return [].

Code

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

class Solution {
public:
    vector<int> movesToStamp(string stamp, string target) {
        int n = target.size(), m = stamp.size();
        string start(n, '?');
        unordered_map<string, vector<int>> movesTo;  // every string reached so far, and the stamps that made it
        movesTo[start] = {};
        queue<string> q;
        q.push(start);
        while (!q.empty()) {
            string s = q.front();
            q.pop();
            if (s == target) return movesTo[s];
            for (int i = 0; i + m <= n; i++) {
                string t = s.substr(0, i) + stamp + s.substr(i + m);  // press the stamp at position i
                if (!movesTo.count(t)) {
                    movesTo[t] = movesTo[s];
                    movesTo[t].push_back(i);
                    q.push(t);
                }
            }
        }
        return {};  // every reachable string was tried and none is the target
    }
};
from collections import deque


class Solution:
    def movesToStamp(self, stamp: str, target: str) -> list[int]:
        n, m = len(target), len(stamp)
        start = '?' * n
        moves_to = {start: []}  # every string reached so far, and the stamps that made it
        queue = deque([start])
        while queue:
            s = queue.popleft()
            if s == target:
                return moves_to[s]
            for i in range(n - m + 1):
                t = s[:i] + stamp + s[i + m:]  # press the stamp at position i
                if t not in moves_to:
                    moves_to[t] = moves_to[s] + [i]
                    queue.append(t)
        return []  # every reachable string was tried and none is the target
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

class Solution {
    public int[] movesToStamp(String stamp, String target) {
        int n = target.length(), m = stamp.length();
        String start = "?".repeat(n);
        Map<String, List<Integer>> movesTo = new HashMap<>();  // every string reached so far, and the stamps that made it
        movesTo.put(start, new ArrayList<>());
        ArrayDeque<String> queue = new ArrayDeque<>();
        queue.add(start);
        while (!queue.isEmpty()) {
            String s = queue.poll();
            if (s.equals(target)) return movesTo.get(s).stream().mapToInt(Integer::intValue).toArray();
            for (int i = 0; i + m <= n; i++) {
                String t = s.substring(0, i) + stamp + s.substring(i + m);  // press the stamp at position i
                if (!movesTo.containsKey(t)) {
                    List<Integer> path = new ArrayList<>(movesTo.get(s));
                    path.add(i);
                    movesTo.put(t, path);
                    queue.add(t);
                }
            }
        }
        return new int[0];  // every reachable string was tried and none is the target
    }
}

Complexity Analysis

Let n = target.length, m = stamp.length, and R the number of strings stamping can make.

Time Complexity: O(R · (n − m + 1) · n). Each string reached tries every position, and building a new string copies n letters.

Space Complexity: O(R · n) to remember every string reached.

R grows exponentially with n. For the stamp "ab", we counted 65 reachable strings at length 6, 1,897 at length 10, 55,405 at length 14, 1.6 million at length 18 and 47 million at length 22.

Why This Approach Is Not Efficient

Visiting all 47 million strings at length 22 took about 130 seconds in Python, and every 4 extra letters multiplied the count by about 29. At length 1000 the search could never finish.

The forward direction is hard because the early stamps are mostly hidden: later stamps overwrite them, so the target says little about them.

Now look at the end instead. The last stamp pressed is never overwritten. It sits in the target completely visible, as a window of m letters that exactly equals the stamp. That can be found directly. Remove it, and the stamp before it becomes the "last" one, visible except where the removed stamp covered it. Working backwards turns the question around: instead of guessing hidden stamps, we keep uncovering visible ones.

Better Approach - Work Backwards, Rescanning Every Window

Intuition

Run the process backwards, peeling stamps off the target one at a time.

A window at position i can be peeled when two things hold:

  1. Every real letter in s[i..i+m−1] equals the stamp's letter in the same place. A ? counts as matching anything.
  2. At least one real letter is left in the window. Otherwise peeling changes nothing.

Peeling turns the whole window into ?. Why ?? The peeled stamp was the last one to touch those spots, so whatever earlier stamps wrote there is hidden and no longer matters. An earlier stamp may leave any letter at all under it. A ? records exactly that: any letter will do.

Keep sweeping the windows from left to right, peeling every one that can be peeled, until a whole sweep peels nothing. If every spot is ?, the peel order read backwards is a valid stamping order. Otherwise the target is impossible.

Example 1 both ways. Peeling backwards from ccatt: the window at 1, cat, is peeled into question marks, then the window at 2, then the window at 0, until only question marks remain. Stamping in the reverse order rebuilds it: at 0 gives cat??, at 2 gives cacat, at 1 gives ccatt. Peeled 1, 2, 0, so the answer is 0, 2, 1.

Four facts make this correct, and none of them needs guessing.

  • The reversed order really makes the target. Stamp in the reverse of the peel order. Take a spot that was still a real letter when its window was peeled. This stamp writes exactly that letter there. No later stamp covers that spot either: every later stamp was peeled earlier, and if one had covered the spot, it would already have been ? at this point. A spot that was already ? is overwritten by a later stamp. Every spot ends up covered, since all of them became ?.
  • Peeling never hurts. Peeling only turns letters into ?, and a ? matches anything. So a window that could be peeled before can still be peeled afterwards, unless it has become all ? and is no longer needed. The order of peeling therefore never matters, and no step ever has to be undone.
  • Getting stuck means impossible. Suppose some valid stamping order existed. Go through its stamps from the last one backwards, and take the first that still covers a real letter. No stamp after it touches those letters, so they are exactly the letters it wrote, and it could be peeled right now. So if nothing can be peeled while real letters remain, no valid order exists.
  • The turn limit is never a problem. A window is peeled at most once, because afterwards it is all ?. There are at most n − m + 1 windows, and n − m + 1 ≤ n ≤ 10 × n.

Step-by-Step Explanation

We trace Example 1, stamp = "cat", target = "ccatt". The window slides over the string each round.

Step 1: Start from the target "ccatt"; nothing is peeled yet.

Step 2: Round 1, window 0 (c c a): "c" at position 1 disagrees with the stamp — skip.

Step 3: Round 1, window 1 (c a t): matches (a ? fits any letter) — peel it. The string becomes "c???t".

Step 4: Round 1, window 2 (? ? t): matches (a ? fits any letter) — peel it. The string becomes "c????".

Step 5: Round 2, window 0 (c ? ?): matches (a ? fits any letter) — peel it. The string becomes "?????".

Step 6: Round 2, window 1 (? ? ?): all ? already — skip.

Step 7: Round 2, window 2 (? ? ?): all ? already — skip.

Step 8: Round 3, window 0 (? ? ?): all ? already — skip.

Step 9: Round 3, window 1 (? ? ?): all ? already — skip.

Step 10: Round 3, window 2 (? ? ?): all ? already — skip. Round 3 peeled nothing, so the search stops.

Step 11: Everything is ?, so reverse the peel order [1, 2, 0] to get [0, 2, 1].

Peeling Backwards, Rescanning Every Window — The window slides over the string each round; green means it matched and was peeled into ?, amber marks the letter that blocks it.

Algorithm

  1. Copy target into a list s. Create an empty list peeled.
  2. Repeat until a full sweep changes nothing:
    • For each i from 0 to n − m: if every non-? letter in s[i..i+m−1] equals the stamp's letter and at least one non-? letter is there, set the window to ? and append i to peeled.
  3. If any real letter is left in s, return [].
  4. Return peeled reversed.

Watch out: without the "at least one real letter" test, an all-? window matches forever. The loop never ends, and the answer fills with useless stamps.

Code

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

class Solution {
    // Every letter must agree with the stamp ('?' agrees with anything), and at least one
    // real letter must remain, or peeling would change nothing and the loop would never end.
    bool canPeel(const string& stamp, const string& s, int i) {
        bool hasLetter = false;
        for (int k = 0; k < (int)stamp.size(); k++) {
            if (s[i + k] == '?') continue;
            if (s[i + k] != stamp[k]) return false;
            hasLetter = true;
        }
        return hasLetter;
    }

public:
    vector<int> movesToStamp(string stamp, string target) {
        int n = target.size(), m = stamp.size();
        string s = target;
        vector<int> peeled;  // windows in the order they are peeled off: the last stamp first
        bool changed = true;
        while (changed) {
            changed = false;
            for (int i = 0; i + m <= n; i++) {
                if (canPeel(stamp, s, i)) {
                    fill(s.begin() + i, s.begin() + i + m, '?');
                    peeled.push_back(i);
                    changed = true;
                }
            }
        }
        if (s != string(n, '?')) return {};  // stuck with real letters left: no order of stamps can make the target
        reverse(peeled.begin(), peeled.end());
        return peeled;
    }
};
class Solution:
    def movesToStamp(self, stamp: str, target: str) -> list[int]:
        n, m = len(target), len(stamp)
        s = list(target)
        peeled = []  # windows in the order they are peeled off: the last stamp first
        changed = True
        while changed:
            changed = False
            for i in range(n - m + 1):
                if self.can_peel(stamp, s, i):
                    s[i:i + m] = ['?'] * m
                    peeled.append(i)
                    changed = True
        if any(c != '?' for c in s):
            return []  # stuck with real letters left: no order of stamps can make the target
        return peeled[::-1]

    def can_peel(self, stamp: str, s: list[str], i: int) -> bool:
        # Every letter must agree with the stamp ('?' agrees with anything), and at least one
        # real letter must remain, or peeling would change nothing and the loop would never end.
        has_letter = False
        for k in range(len(stamp)):
            if s[i + k] == '?':
                continue
            if s[i + k] != stamp[k]:
                return False
            has_letter = True
        return has_letter
import java.util.ArrayList;
import java.util.List;

class Solution {
    public int[] movesToStamp(String stamp, String target) {
        int n = target.length(), m = stamp.length();
        char[] s = target.toCharArray();
        List<Integer> peeled = new ArrayList<>();  // windows in the order they are peeled off: the last stamp first
        boolean changed = true;
        while (changed) {
            changed = false;
            for (int i = 0; i + m <= n; i++) {
                if (canPeel(stamp, s, i)) {
                    for (int k = 0; k < m; k++) s[i + k] = '?';
                    peeled.add(i);
                    changed = true;
                }
            }
        }
        for (char c : s)
            if (c != '?') return new int[0];  // stuck with real letters left: no order of stamps can make the target
        int[] order = new int[peeled.size()];
        for (int k = 0; k < order.length; k++) order[k] = peeled.get(order.length - 1 - k);
        return order;
    }

    // Every letter must agree with the stamp ('?' agrees with anything), and at least one
    // real letter must remain, or peeling would change nothing and the loop would never end.
    private boolean canPeel(String stamp, char[] s, int i) {
        boolean hasLetter = false;
        for (int k = 0; k < stamp.length(); k++) {
            if (s[i + k] == '?') continue;
            if (s[i + k] != stamp.charAt(k)) return false;
            hasLetter = true;
        }
        return hasLetter;
    }
}

Complexity Analysis

Let n = target.length and m = stamp.length.

Time Complexity: O((n − m + 1)² · m). One sweep checks n − m + 1 windows at up to m letters each, and every sweep but the last peels at least one window, so there are at most n − m + 1 sweeps. The slowest input we found at full size stamps every position from left to right with a random 333-letter stamp, which forces one peel per sweep. It took about 0.95 s in Python.

Space Complexity: O(n) for the working copy and the list of peels.

Why This Approach Is Not Efficient

Most of each sweep is wasted. After a peel, the only windows whose status can change are the ones that overlap the spots that just became ?, at most 2m − 1 of them. Every other window gets rechecked letter by letter and gives the same answer as before.

So what does a window actually wait for? It becomes peelable exactly when every position where the target disagrees with the stamp has turned into ?. If each window keeps a count of how many of its disagreeing positions are still letters, a newly blanked position only needs to lower the counts of the windows covering it. A window whose count reaches 0 is ready, and it can go straight into a queue. Nothing ever needs a second sweep.

Optimal Approach - Work Backwards With Disagreement Counts and a Queue

Intuition

Set up, for every window i, a count left[i]: the number of positions j in the window where target[j] differs from the stamp's letter. A window with left[i] = 0 matches the target exactly, so it could be the last stamp. Put every such window into a queue.

Then repeat until the queue is empty:

  1. Take window i from the queue and record it. It is the next stamp, counting from the last.
  2. Turn each of its positions that is still a letter into ?. For each such position p, look at every not-yet-peeled window w that covers p. If p was one of w's disagreements, lower left[w] by 1. When left[w] reaches 0, all of w's disagreements are now ?, so w can be peeled, and it joins the queue.

At the end, if every position became ?, reverse the recorded order. Otherwise return []. This is the same peeling as before, with the same four reasons it is correct, but each position turns into ? once and each (position, window) pair is looked at once.

One harmless detail: a window can join the queue with all its positions already ?. Recording it adds a stamp that later stamps completely cover. That is still valid, and each window is recorded at most once.

Step-by-Step Explanation

We trace Example 1 again. The string on top turns into ? as windows are peeled; the table below it holds each window's count of positions still disagreeing with the stamp.

Step 1: Count disagreements per window: window 0 has 2, window 1 has 0, window 2 has 2. Put window 1 in the queue.

Step 2: Take window 1 from the queue and record it; order so far [1].

Step 3: Position 1 becomes ?: window 0 now has 1 left.

Step 4: Position 2 becomes ?: window 0 now has 0 left and joins the queue; window 2 now has 1 left.

Step 5: Position 3 becomes ?: window 2 now has 0 left and joins the queue.

Step 6: Take window 0 from the queue and record it; order so far [1, 0]. Position 0 becomes ?; no other window was waiting on it.

Step 7: Take window 2 from the queue and record it; order so far [1, 0, 2]. Position 4 becomes ?; no other window was waiting on it.

Step 8: Every position is ?. Reverse [1, 0, 2] to get [2, 0, 1].

Disagreement Counts and a Queue — The string on top turns into ? as windows are peeled; the table counts, for each window, how many of its positions still disagree with the stamp.

Algorithm

  1. For each window i from 0 to n − m, set left[i] = the number of j in [i, i + m) with target[j] ≠ stamp[j − i].
  2. Put every window with left[i] = 0 in a queue and mark it peeled.
  3. While the queue is not empty:
    • Take i, append it to order.
    • For each position p from i to i + m − 1 that is not yet ?:
      • Mark p as ?.
      • For each unpeeled window w with p − m + 1 ≤ w ≤ p (inside the valid range) and target[p] ≠ stamp[p − w]: decrease left[w]. If it becomes 0, mark w peeled and add it to the queue.
  4. If some position was never marked ?, return []. Otherwise return order reversed.

Code

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

class Solution {
public:
    vector<int> movesToStamp(string stamp, string target) {
        int n = target.size(), m = stamp.size(), windows = n - m + 1;
        // left[i]: how many positions still differ between the target and a stamp placed at i
        vector<int> left(windows, 0);
        for (int i = 0; i < windows; i++)
            for (int j = i; j < i + m; j++)
                if (target[j] != stamp[j - i]) left[i]++;
        vector<bool> peeled(windows, false), blank(n, false);
        queue<int> q;
        for (int i = 0; i < windows; i++)
            if (left[i] == 0) {
                peeled[i] = true;
                q.push(i);
            }
        vector<int> order;  // the last stamp first
        while (!q.empty()) {
            int i = q.front();
            q.pop();
            order.push_back(i);
            for (int p = i; p < i + m; p++) {
                if (blank[p]) continue;
                blank[p] = true;
                // p is now '?', so it no longer disagrees with any window that covers it
                for (int w = max(0, p - m + 1); w <= min(p, windows - 1); w++) {
                    if (peeled[w] || target[p] == stamp[p - w]) continue;
                    if (--left[w] == 0) {
                        peeled[w] = true;
                        q.push(w);
                    }
                }
            }
        }
        for (bool b : blank)
            if (!b) return {};  // some letter could never be peeled: no order of stamps can make the target
        reverse(order.begin(), order.end());
        return order;
    }
};
from collections import deque


class Solution:
    def movesToStamp(self, stamp: str, target: str) -> list[int]:
        n, m = len(target), len(stamp)
        windows = n - m + 1
        # left[i]: how many positions still differ between the target and a stamp placed at i
        left = [sum(1 for j in range(i, i + m) if target[j] != stamp[j - i]) for i in range(windows)]
        peeled = [False] * windows
        blank = [False] * n  # has this position become '?'
        queue = deque()
        for i in range(windows):
            if left[i] == 0:
                peeled[i] = True
                queue.append(i)
        order = []  # the last stamp first
        while queue:
            i = queue.popleft()
            order.append(i)
            for p in range(i, i + m):
                if blank[p]:
                    continue
                blank[p] = True
                # p is now '?', so it no longer disagrees with any window that covers it
                for w in range(max(0, p - m + 1), min(p, windows - 1) + 1):
                    if peeled[w] or target[p] == stamp[p - w]:
                        continue
                    left[w] -= 1
                    if left[w] == 0:
                        peeled[w] = True
                        queue.append(w)
        if not all(blank):
            return []  # some letter could never be peeled: no order of stamps can make the target
        return order[::-1]
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.List;

class Solution {
    public int[] movesToStamp(String stamp, String target) {
        int n = target.length(), m = stamp.length(), windows = n - m + 1;
        // left[i]: how many positions still differ between the target and a stamp placed at i
        int[] left = new int[windows];
        for (int i = 0; i < windows; i++)
            for (int j = i; j < i + m; j++)
                if (target.charAt(j) != stamp.charAt(j - i)) left[i]++;
        boolean[] peeled = new boolean[windows], blank = new boolean[n];
        ArrayDeque<Integer> queue = new ArrayDeque<>();
        for (int i = 0; i < windows; i++)
            if (left[i] == 0) {
                peeled[i] = true;
                queue.add(i);
            }
        List<Integer> order = new ArrayList<>();  // the last stamp first
        while (!queue.isEmpty()) {
            int i = queue.poll();
            order.add(i);
            for (int p = i; p < i + m; p++) {
                if (blank[p]) continue;
                blank[p] = true;
                // p is now '?', so it no longer disagrees with any window that covers it
                for (int w = Math.max(0, p - m + 1); w <= Math.min(p, windows - 1); w++) {
                    if (peeled[w] || target.charAt(p) == stamp.charAt(p - w)) continue;
                    if (--left[w] == 0) {
                        peeled[w] = true;
                        queue.add(w);
                    }
                }
            }
        }
        for (boolean b : blank)
            if (!b) return new int[0];  // some letter could never be peeled: no order of stamps can make the target
        int[] result = new int[order.size()];
        for (int k = 0; k < result.length; k++) result[k] = order.get(result.length - 1 - k);
        return result;
    }
}

Complexity Analysis

Let n = target.length and m = stamp.length.

Time Complexity: O((n − m + 1) · m).

  • Setting up the counts compares each window with the stamp once: (n − m + 1) · m.
  • Each position turns into ? at most once, and it then visits at most m windows.

On the slowest input for the rescanning version above, this took about 0.03 s in Python, roughly 30 times faster.

Space Complexity: O(n) for the counts, the flags, the queue and the order.