Stamping The Sequence

Hard

#0890Time: O(N * (N-M) * M), where N is the length of `target` and M is the length of `stamp`. The outer `while` loop can run up to N times in the worst case (if we only replace one character at a time). Inside the loop, we iterate through `N-M` possible windows, and for each window, we perform a check and a replacement, both taking O(M) time. This leads to a cubic complexity in the worst-case scenarios.Space: O(N), where N is the length of `target`. This space is used to store the character array for the target, the result list, and the visited array.1 company

Patterns

Greedy

Data structures

String Stack Queue

Companies

Morgan Stanley

Prompt

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.

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 <= 1000
stamp and target consist of lowercase English letters.

Approaches

2 approaches with complexity analysis and trade-offs.

This approach simulates the stamping process in reverse. Instead of building the target string from a string of question marks, we start with the target string and try to 'un-stamp' it back to a string of all question marks. The core idea is that the last stamp applied must have perfectly matched a substring of the final target. By repeatedly finding such matches and replacing them with question marks, we can reverse the entire process.

Algorithm

Initialize a character array tChars from the target string, a list result to store stamp indices, and a count stars of characters replaced by '?'.
Create a boolean array visited of size target.length - stamp.length + 1 to avoid processing the same window multiple times.
Loop continuously as long as progress is made in a round (stars < target.length):
- Set a flag replacedInRound to false at the beginning of each pass.
- Iterate through all possible starting positions i for the stamp from 0 to n-m.
- If window i has not been visited and can be 'unstamped', proceed.
- A window can be unstamped if every character in the window either matches the corresponding character in stamp or is already a '?'.
- If a valid window is found at i, replace the characters in that window with '?', add i to the result list, mark i as visited, and update the stars count. Only add i to the result if at least one new character was replaced to ensure progress.
- Set replacedInRound to true.
- If a full pass over all windows yields no new unstamps (replacedInRound remains false), then it's impossible to solve.
If the loop completes and stars equals the length of target, it means we have successfully converted the entire string to '?'. The sequence of operations is the result list in reverse order.
If it's impossible, return an empty array.

Walkthrough

The algorithm works by repeatedly scanning the target string for substrings that could have been placed by the stamp. When such a substring is found, it's replaced with '?' characters, signifying that this part of the target is now 'explained'. This process continues until the entire string becomes '?'s. The indices of these replacements, when reversed, give a valid sequence of stamping operations.

1import java.util.ArrayList;2import java.util.Collections;3import java.util.List;4 5class Solution {6    public int[] movesToStamp(String stamp, String target) {7        char[] sChars = stamp.toCharArray();8        char[] tChars = target.toCharArray();9        int n = tChars.length;10        int m = sChars.length;11        List<Integer> result = new ArrayList<>();12        boolean[] visited = new boolean[n - m + 1];13        int stars = 0;14 15        while (stars < n) {16            boolean replacedInRound = false;17            for (int i = 0; i <= n - m; i++) {18                if (!visited[i] && canReplace(tChars, i, sChars)) {19                    int newStars = doReplace(tChars, i, m);20                    if (newStars > 0) {21                        stars += newStars;22                        replacedInRound = true;23                        visited[i] = true;24                        result.add(i);25                    }26                }27            }28            if (!replacedInRound) {29                return new int[0];30            }31        }32 33        Collections.reverse(result);34        return result.stream().mapToInt(i -> i).toArray();35    }36 37    private boolean canReplace(char[] tChars, int start, char[] sChars) {38        for (int i = 0; i < sChars.length; i++) {39            if (tChars[start + i] != '?' && tChars[start + i] != sChars[i]) {40                return false;41            }42        }43        return true;44    }45 46    private int doReplace(char[] tChars, int start, int len) {47        int count = 0;48        for (int i = 0; i < len; i++) {49            if (tChars[start + i] != '?') {50                tChars[start + i] = '?';51                count++;52            }53        }54        return count;55    }56}

Complexity

Time

O(N * (N-M) * M), where N is the length of `target` and M is the length of `stamp`. The outer `while` loop can run up to N times in the worst case (if we only replace one character at a time). Inside the loop, we iterate through `N-M` possible windows, and for each window, we perform a check and a replacement, both taking O(M) time. This leads to a cubic complexity in the worst-case scenarios.

Space

O(N), where N is the length of `target`. This space is used to store the character array for the target, the result list, and the visited array.

Trade-offs

Pros

Relatively simple to understand and implement.
Low space complexity.

Cons

The time complexity is high, potentially leading to a 'Time Limit Exceeded' error on larger inputs.

This approach significantly optimizes the brute-force method by avoiding redundant checks. Instead of scanning the entire string repeatedly, we identify which windows are ready to be 'unstamped' and process them in a queue. An unstamp operation at one position can make adjacent or overlapping windows ready. We track these dependencies to efficiently find the next window to process.

Algorithm

Initialization:
- Create a todo array, where todo[i] stores the number of characters in the window starting at i that do not match the stamp.
- Create a dependency map affects, where affects[p] is a list of all window indices that cover character position p.
- Initialize a queue and add all window indices i that are ready from the start (i.e., todo[i] == 0). Mark these as visited.
Processing:
- While the queue is not empty, dequeue a window index i. This is a window we are 'unstamping'. Add i to the result list.
- For each character position p within the window i:
  - If p has not been stamped to '?' yet, mark it as done.
  - This change might make other windows ready. For every window j that is affected by the change at p (i.e., j is in affects[p]):
    - Decrement todo[j].
    - If todo[j] becomes 0, it means window j is now a perfect match with the (partially '?'d) string. Add j to the queue and mark it as visited.
Finalization:
- After the queue is empty, check if all N characters have been turned to '?'.
- If yes, the result list contains the sequence of stamp indices in reverse order. Reverse it and return.
- If not, a solution is not possible, so return an empty array.

Walkthrough

This optimized method avoids the expensive re-scanning of the entire string. It first preprocesses the target to understand the relationships between character positions and stamp windows.

Specifically, for each possible stamp window, we count how many characters currently mismatch the stamp. These are windows that are not yet ready. For each character position, we also list all windows that cover it. When a window becomes ready (mismatches drop to zero), we process it. Processing involves marking its characters as ?, and for each newly marked ?, we update the mismatch count of all other windows that covered this character. This might make new windows ready, which are then added to a queue for processing.

1import java.util.ArrayList;2import java.util.Collections;3import java.util.LinkedList;4import java.util.List;5import java.util.Queue;6 7class Solution {8    public int[] movesToStamp(String stamp, String target) {9        int m = stamp.length();10        int n = target.length();11        char[] sChars = stamp.toCharArray();12        char[] tChars = target.toCharArray();13 14        List<Integer>[] affects = new ArrayList[n];15        for (int i = 0; i < n; i++) {16            affects[i] = new ArrayList<>();17        }18 19        int[] todo = new int[n - m + 1];20        Queue<Integer> queue = new LinkedList<>();21        boolean[] visited = new boolean[n - m + 1];22 23        for (int i = 0; i <= n - m; i++) {24            for (int j = 0; j < m; j++) {25                if (tChars[i + j] != sChars[j]) {26                    todo[i]++;27                }28            }29            if (todo[i] == 0) {30                queue.offer(i);31                visited[i] = true;32            }33            for (int j = 0; j < m; j++) {34                affects[i + j].add(i);35            }36        }37 38        List<Integer> result = new ArrayList<>();39        boolean[] done = new boolean[n];40        int stampedCount = 0;41 42        while (!queue.isEmpty()) {43            int i = queue.poll();44            result.add(i);45 46            for (int j = 0; j < m; j++) {47                int k = i + j;48                if (!done[k]) {49                    done[k] = true;50                    stampedCount++;51                    for (int p : affects[k]) {52                        if (!visited[p]) {53                            todo[p]--;54                            if (todo[p] == 0) {55                                queue.offer(p);56                                visited[p] = true;57                            }58                        }59                    }60                }61            }62        }63 64        if (stampedCount != n) {65            return new int[0];66        }67 68        Collections.reverse(result);69        return result.stream().mapToInt(i -> i).toArray();70    }71}

Complexity

Time

O(N*M), where N is the length of `target` and M is the length of `stamp`. The initialization phase takes O((N-M)*M) to compute `todo` counts and build the `affects` map. The processing phase is also O(N*M) in total, because each character `k` is marked `done` once, and when it is, we iterate through `affects[k]`, which has size at most M. The total work across all characters is bounded by the total number of dependencies, which is (N-M+1)*M.

Space

O(N*M) to store the `affects` dependency map. In the worst case (e.g., M is close to N/2), this can be substantial. Other data structures like `todo`, `queue`, and `done` take O(N) space.

Trade-offs

Pros

Significantly more time-efficient than the brute-force approach.
Guaranteed to pass within the time limits for the given constraints.

Cons

Requires more complex data structures.
Has a higher space complexity, which could be a concern for very large inputs, though it's acceptable for the given constraints.

Solutions

Solution

1class Solution {2public3  int[] movesToStamp(String stamp, String target) {4    int m = stamp.length(), n = target.length();5    int[] indeg = new int[n - m + 1];6    Arrays.fill(indeg, m);7    List<Integer>[] g = new List[n];8    Arrays.setAll(g, i->new ArrayList<>());9    Deque<Integer> q = new ArrayDeque<>();10    for (int i = 0; i < n - m + 1; ++i) {11      for (int j = 0; j < m; ++j) {12        if (target.charAt(i + j) == stamp.charAt(j)) {13          if (--indeg[i] == 0) {14            q.offer(i);15          }16        } else {17          g[i + j].add(i);18        }19      }20    }21    List<Integer> ans = new ArrayList<>();22    boolean[] vis = new boolean[n];23    while (!q.isEmpty()) {24      int i = q.poll();25      ans.add(i);26      for (int j = 0; j < m; ++j) {27        if (!vis[i + j]) {28          vis[i + j] = true;29          for (int k : g[i + j]) {30            if (--indeg[k] == 0) {31              q.offer(k);32            }33          }34        }35      }36    }37    for (int i = 0; i < n; ++i) {38      if (!vis[i]) {39        return new int[0];40      }41    }42    Collections.reverse(ans);43    return ans.stream().mapToInt(Integer : : intValue).toArray();44  }45}

1class Solution {2public:3  vector<int> movesToStamp(string stamp, string target) {4    int m = stamp.size(), n = target.size();5    vector<int> indeg(n - m + 1, m);6    vector<int> g[n];7    queue<int> q;8    for (int i = 0; i < n - m + 1; ++i) {9      for (int j = 0; j < m; ++j) {10        if (target[i + j] == stamp[j]) {11          if (--indeg[i] == 0) {12            q.push(i);13          }14        } else {15          g[i + j].push_back(i);16        }17      }18    }19    vector<int> ans;20    vector<bool> vis(n);21    while (q.size()) {22      int i = q.front();23      q.pop();24      ans.push_back(i);25      for (int j = 0; j < m; ++j) {26        if (!vis[i + j]) {27          vis[i + j] = true;28          for (int k : g[i + j]) {29            if (--indeg[k] == 0) {30              q.push(k);31            }32          }33        }34      }35    }36    for (int i = 0; i < n; ++i) {37      if (!vis[i]) {38        return {};39      }40    }41    reverse(ans.begin(), ans.end());42    return ans;43  }44};

1class Solution:2    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 []

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next problem