936. Stamping The Sequence
Problem Description
The problem presents us with a stamping process where a stamp
is used to convert a string of question marks s
, which is initially the same length as a given target
string. The goal is to achieve the target configuration by placing the stamp over s
in such a way that each letter in s
is replaced by the corresponding letter from stamp
. The challenge is that you cannot stamp beyond the boundaries of s
and must complete the stamping process within a certain number of turns (at most 10
times the length of the target string).
A successful stamping means you've found a way to completely transform the string of question marks into the desired target
string using the given stamp
. The problem asks for an array of indices indicating where the stamp was placed during each turn if the transformation is possible. If it's not possible to achieve the target
string from s
within the given turns, an empty array should be returned.
Intuition
To solve this problem, we approach it from the reverse direction. Instead of trying to build the target
from a string of question marks, we try to deconstruct the target
into a string of question marks using the stamp
. This reverse thinking simplifies the process since it eliminates the complications that arise from the fact that stamping on one part of the string could overwrite previous changes.
The solution uses the idea of topological sorting, which allows us to keep track of where the stamp
can be placed based on the current configuration of target
. This approach breaks down the problem into manageable parts:
- We identify "windows" in the
target
string where thestamp
could fit (each window being the length of thestamp
). - We determine how many characters within each window do not match the
stamp
(using the in-degree arrayindeg
). - We create an adjacency list
g
to track the dependencies between different windows. - We use a queue
q
to process each window that can be stamped (has an in-degree of0
). - We maintain an array
vis
to mark whether we've successfully stamped that portion of thetarget
. - The answer array
ans
captures the sequence of stamp placements (indexed by the left-most letter of each stamp).
By virtually "unstamping" the target
until it turns into a string of question marks, we effectively capture the required stamp placement sequence. If every position of the target
is visited during the "unstamping," then target
can be constructed from the question mark string. Otherwise, if any position is left uncovered, it's not possible to achieve the target
using the stamp, and thereby an empty array is returned.
Solution Approach
The solution involves reversing the stamping problem and applying topological sorting techniques. Let's walk through the key components of the implementation:
Data Structures:
-
In-degree array
indeg
: This array tracks the differences between thestamp
and each window of thetarget
. A window is a substring oftarget
that has the same length asstamp
. Whenindeg[i]
is zero, it means thei
th window matches thestamp
perfectly, and we can consider "unstamping" from this point. -
Adjacency list
g
: This list represents the dependencies between different windows and the positions in thetarget
string. Specifically,g[i]
holds a list of window starts where the characters at positioni
intarget
don't match thestamp
. So if we change thei
th character intarget
, we need to update these windows. -
Queue
q
: This is used to hold window start positions where the in-degree is zero, indicating they are ready to be "unstamped" because they match thestamp
. -
Visited array
vis
: This boolean array keeps track of whether each character has been covered by the "unstamping" process. -
Answer list
ans
: This list captures the sequence of positions where thestamp
was used during the reverse process.
Algorithm:
-
Initialization:
- Set each entry of
indeg
to the length of thestamp
, since this is the number of characters that must match to "unstamp." - Populate the adjacency list
g
by comparing each character of each window to the corresponding character in thestamp
. If they don't match, add the window's start position tog[i]
.
- Set each entry of
-
Topological sorting:
- Push the indices of windows with an in-degree of zero (fully matching windows) into the queue.
- While the queue isn't empty, repeatedly remove window start indices from the front of the queue and append them to
ans
. - For each character position
j
in the window which is not visited (vis[i + j]
isFalse
), markvis[i + j]
asTrue
. - After marking a character position as stamped, go through all the windows listed in
g[i + j]
and decrease their in-degree by one (since now they have one more character matching thestamp
). - If reducing the in-degree of any window makes it zero, push that window's start index into the queue, since it's ready for "unstamping."
-
Final check and output:
- After the topological sort is done, we check if every position of the
target
has been visited. - If so, reversing
ans
gives the order in which we would stamp to buildtarget
from a string of question marks. - If there are positions that we did not visit, it means the
target
string cannot be covered by thestamp
within the constraints, and we return an empty list.
- After the topological sort is done, we check if every position of the
By following this approach, we utilize the properties of topological sorting to systematically determine where we can place our stamp in the reverse order, ultimately revealing the sequence needed to construct the target
from a string of question marks, if at all possible.
Ready to land your dream job?
Unlock your dream job with a 2-minute evaluator for a personalized learning plan!
Start EvaluatorExample Walkthrough
Let's use a small example to illustrate the solution approach. Suppose we have a stamp
of "abc" and a target
of "ababc". The goal is to find a sequence of stamp placements that can transform a string of question marks "?????" into the target
"ababc".
-
Initialization:
- Our
indeg
array will start with[3, 3, 3, 3, 3]
because each window needs to match 3 characters of the stamp. g
adjacency list will be empty initially because we haven't compared windows in the target to the stamp yet.vis
array will be[False, False, False, False, False]
, indicating no character has been stamped yet.- And,
ans
list will be empty as we have not performed any "unstamping" operations.
- Our
-
Building adjacency list (
g
) and initializingindeg
:- We compare substrings (or windows) of
target
withstamp
:- Window "aba" (from position 0 to 2) has 2 characters matching with
stamp
"abc", henceindeg[0] = 1
. - Window "bab" (from position 1 to 3) has 0 characters matching with
stamp
"abc", henceindeg[1] = 3
. - Window "abc" (from position 2 to 4) is a perfect match, hence
indeg[2] = 0
.
- Window "aba" (from position 0 to 2) has 2 characters matching with
- Update
g
: For window "aba", we will add 0 tog[1]
because if the second character ('b') changes, the window will be affected.
- We compare substrings (or windows) of
-
Topological sorting:
- Only window "abc" matches the
stamp
completely (indeg[2]
is 0), so we add its starting index 2 to the queue. - We process
q
and remove the start index 2, appending it toans
(so nowans = [2]
). - We mark all
vis
positions within this window as 'True', sovis
becomes[False, False, True, True, True]
. - Since window "bab" (1 to 3) includes characters at positions 2 and 3 which we just marked as True, we reduce
indeg[1]
to 1 (because those positions now match thestamp
due to "unstamping").
- Only window "abc" matches the
-
Continuing topological sorting:
- With
indeg[1]
updated, it's still not 0, so we continue. - Now we attempt to match window "aba" with
stamp
"abc". Since the character at position 1 ('b') changes, we need to checkg[1]
, which tells us to update the window starting at 0. - We reduce
indeg[0]
by 1 and now it becomes 0. - We push 0 to
q
because now the first window "aba" fully matchesstamp
after "unstamping" "abc". - Again, we remove the front of the queue (0), append it to
ans
(so nowans = [2, 0]
), and mark all of itsvis
positions as True.
- With
-
Final check and output:
- Now
vis
is[True, True, True, True, True]
, which means every character intarget
has been "unstamped". - When reversed,
ans
becomes[0, 2]
. This is the sequence of stamp placements in reverse; to buildtarget
from the string of question marks, we stamp at index 0 first and then at index 2.
- Now
By following this approach, we conclude that the given target
"ababc" can be achieved from "?????" by stamping "abc" at index 0 and then at index 2. The solution correctly returns [0, 2]
as the sequence of stamp placements.
Solution Implementation
1from collections import deque
2from typing import List
3
4class Solution:
5 def movesToStamp(self, stamp: str, target: str) -> List[int]:
6 # Length of the stamp and the target strings
7 stamp_length, target_length = len(stamp), len(target)
8 # Initialize indegrees to length of the stamp for all possible stamp positions in target
9 indegrees = [stamp_length] * (target_length - stamp_length + 1)
10 queue = deque()
11 # Graph to keep track of the possible moves
12 graph = [[] for _ in range(target_length)]
13
14 # Preprocessing to fill indegrees and graph:
15 # Inspecting each possible window in the target where the stamp could be placed
16 for i in range(target_length - stamp_length + 1):
17 for j, char in enumerate(stamp):
18 if target[i + j] == char:
19 # Decrease indegree if the character matches
20 indegrees[i] -= 1
21 # If all characters match, we can place a stamp here,
22 # thus we add it to the queue
23 if indegrees[i] == 0:
24 queue.append(i)
25 else:
26 # If characters do not match, we record the dependency in the graph
27 graph[i + j].append(i)
28
29 result = []
30 visited = [False] * target_length
31
32 # Process the stamps in queue and update the graph accordingly
33 while queue:
34 position = queue.popleft()
35 result.append(position)
36 for j in range(stamp_length):
37 if not visited[position + j]:
38 visited[position + j] = True
39 for dependency in graph[position + j]:
40 # Once a stamp is placed, we update dependencies and
41 # possibly add new stamp positions to the queue
42 indegrees[dependency] -= 1
43 if indegrees[dependency] == 0:
44 queue.append(dependency)
45
46 # If all characters have been stamped (visited), return the result in reversed order
47 # because we need the sequence of moves from the beginning, not the end.
48 # Otherwise, return an empty list if it's not possible to stamp the target completely.
49 return result[::-1] if all(visited) else []
50
51# Example usage:
52# solution = Solution()
53# result = solution.movesToStamp("abca", "aabcaca")
54# print(result) # Output should be the sequence of moves to complete the stamping
55
1import java.util.Arrays;
2import java.util.ArrayDeque;
3import java.util.ArrayList;
4import java.util.Deque;
5import java.util.List;
6import java.util.Collections;
7
8class Solution {
9 public int[] movesToStamp(String stamp, String target) {
10 int stampLength = stamp.length(), targetLength = target.length();
11
12 // Array to keep track of how many characters each substring needs
13 // to become a stamp starting from that position.
14 int[] inDegrees = new int[targetLength - stampLength + 1];
15 Arrays.fill(inDegrees, stampLength);
16
17 // Graph to store the dependencies between the substrings of 'target' and 'stamp'
18 List<Integer>[] graph = new List[targetLength];
19 Arrays.setAll(graph, i -> new ArrayList<>());
20
21 // Queue to perform a BFS
22 Deque<Integer> queue = new ArrayDeque<>();
23
24 // Build the graph based on matching characters and fill in the queue
25 for (int i = 0; i <= targetLength - stampLength; ++i) {
26 for (int j = 0; j < stampLength; ++j) {
27 if (target.charAt(i + j) == stamp.charAt(j)) {
28 // If characters match, reduce the in-degree count
29 if (--inDegrees[i] == 0) {
30 queue.offer(i);
31 }
32 } else {
33 // If characters don't match, add the dependency edge
34 graph[i + j].add(i);
35 }
36 }
37 }
38
39 // List to store the sequence of moves in reverse order
40 List<Integer> answerList = new ArrayList<>();
41
42 // Visited array to keep track of processed characters
43 boolean[] visited = new boolean[targetLength];
44
45 // Perform BFS
46 while (!queue.isEmpty()) {
47 int i = queue.poll();
48 answerList.add(i);
49 for (int j = 0; j < stampLength; ++j) {
50 if (!visited[i + j]) {
51 visited[i + j] = true;
52 for (int k : graph[i + j]) {
53 if (--inDegrees[k] == 0) {
54 queue.offer(k);
55 }
56 }
57 }
58 }
59 }
60
61 // Verify if all characters of target have been stamped
62 for (int i = 0; i < targetLength; ++i) {
63 if (!visited[i]) {
64 return new int[0];
65 }
66 }
67
68 // Since answerList contains the sequence in reverse order, we need to reverse it
69 Collections.reverse(answerList);
70
71 // Convert the List to an array and return
72 return answerList.stream().mapToInt(Integer::intValue).toArray();
73 }
74}
75
1#include <vector>
2#include <queue>
3#include <string>
4#include <algorithm>
5
6class Solution {
7public:
8 std::vector<int> movesToStamp(std::string stamp, std::string target) {
9 int stampLength = stamp.size(), targetLength = target.size();
10 std::vector<int> inDegree(targetLength - stampLength + 1, stampLength);
11 std::vector<int> graph[targetLength];
12 std::queue<int> queue;
13
14 // Construct graph where each node represents a position in the target
15 // that can potentially be stamped.
16 for (int i = 0; i <= targetLength - stampLength; ++i) {
17 for (int j = 0; j < stampLength; ++j) {
18 // If the character matches, decrease in-degree of that node,
19 // otherwise add an edge to the dependency graph.
20 if (target[i + j] == stamp[j]) {
21 if (--inDegree[i] == 0) {
22 queue.push(i);
23 }
24 } else {
25 graph[i + j].push_back(i);
26 }
27 }
28 }
29
30 std::vector<int> result;
31 std::vector<bool> visited(targetLength, false);
32
33 // Process nodes with zero in-degree and add valid ones to the result.
34 while (!queue.empty()) {
35 int index = queue.front();
36 queue.pop();
37 result.push_back(index);
38 for (int j = 0; j < stampLength; ++j) {
39 if (!visited[index + j]) {
40 visited[index + j] = true;
41 // Decrement in-degree of dependent nodes and if it becomes zero,
42 // add it to the queue for processing.
43 for (int dependentIndex : graph[index + j]) {
44 if (--inDegree[dependentIndex] == 0) {
45 queue.push(dependentIndex);
46 }
47 }
48 }
49 }
50 }
51
52 // Check if all characters in the target have been visited (stamped).
53 // If not all characters are visited, it's not possible to stamp the target.
54 for (bool isVisited : visited) {
55 if (!isVisited) {
56 return {};
57 }
58 }
59
60 // Reverse the result as we want to return the sequence of moves
61 // in the order they would be applied to the target.
62 std::reverse(result.begin(), result.end());
63 return result;
64 }
65};
66
1function movesToStamp(stamp: string, target: string): number[] {
2 const stampLength: number = stamp.length;
3 const targetLength: number = target.length;
4
5 // Initialize an array to hold the indegree of each substring of the target starting at each position
6 const indegree: number[] = Array(targetLength - stampLength + 1).fill(stampLength);
7
8 // Graph to hold the relationship of each character in target affected by the stamping process
9 const graph: number[][] = Array.from({ length: targetLength }, () => []);
10
11 // Queue for positions of the target that are ready to be stamped
12 const queue: number[] = [];
13
14 // Preprocess: Fill the graph with dependencies and prepare the queue with start positions
15 for (let i = 0; i <= targetLength - stampLength; ++i) {
16 for (let j = 0; j < stampLength; ++j) {
17 // If the current stamp character matches the target character, decrement indegree
18 if (target[i + j] === stamp[j]) {
19 if (--indegree[i] === 0) {
20 queue.push(i);
21 }
22 } else {
23 // If there is a mismatch, record a dependency
24 graph[i + j].push(i);
25 }
26 }
27 }
28
29 // Array to hold the sequence of stamp positions
30 const resultSequence: number[] = [];
31
32 // Array to track visited positions
33 const visited: boolean[] = Array(targetLength).fill(false);
34
35 // Process the queue
36 while (queue.length) {
37 const currentPosition: number = queue.shift()!;
38 resultSequence.push(currentPosition);
39 for (let j = 0; j < stampLength; ++j) {
40 if (!visited[currentPosition + j]) {
41 visited[currentPosition + j] = true;
42 // Decrement indegrees for other positions dependent on this one
43 for (const dependentPosition of graph[currentPosition + j]) {
44 if (--indegree[dependentPosition] === 0) {
45 queue.push(dependentPosition);
46 }
47 }
48 }
49 }
50 }
51
52 // If not all positions have been visited, return an empty array as it's not possible to stamp
53 if (!visited.every(v => v)) {
54 return [];
55 }
56
57 // Reverse the result sequence since we stamp from end to beginning
58 resultSequence.reverse();
59
60 return resultSequence;
61}
62
Time and Space Complexity
The time complexity of the given code is O(n * (n - m + 1))
. This is because for each position in the target string target
, we check if it can be stamped by the stamp, which involves comparing each character in the stamp to the corresponding characters in target
. This comparison takes O(m)
time per position, and there are up to n - m + 1
positions where a stamp could be applied, leading to O(m * (n - m + 1))
operations. Since m
is a constant compared to n
as n
grows larger, the complexity simplifies to O(n * (n - m + 1))
.
The space complexity of the code is also O(n * (n - m + 1))
. This is due to the construction of the graph g
, which for each character in the target
string (n
characters), stores a list of indices where the stamp
does not match, and this can happen for up to each position in the range 0
to n - m
. Thus, the space taken by g
can be up to n * (n - m + 1)
. Additionally, there is a constant amount of space used by auxiliary variables, which does not affect the overall space complexity.
Learn more about how to find time and space complexity quickly using problem constraints.
Consider the classic dynamic programming of longest increasing subsequence:
Find the length of the longest subsequence of a given sequence such that all elements of the subsequence are sorted in increasing order.
For example, the length of LIS for [50, 3, 10, 7, 40, 80]
is 4
and LIS is
[3, 7, 40, 80]
.
What is the recurrence relation?
Recommended Readings
Stack Intro Imagine you have a pile of books on your desk If you want to add a new book you place it on top If you want to read a book you take it from the top And if you simply want to see which book is on the top you
Greedy Introduction div class responsive iframe iframe src https www youtube com embed WTslqPbj7I title YouTube video player frameborder 0 allow accelerometer autoplay clipboard write encrypted media gyroscope picture in picture web share allowfullscreen iframe div When do we use greedy Greedy algorithms tend to solve optimization problems Typically they will ask you to calculate the max min of some value Commonly you may see this phrased in the problem as max min longest shortest largest smallest etc These keywords can be identified by just scanning
Queue Intro Think of the last time you stood in line to buy movie tickets The first person in line gets their ticket first and any newcomers join the end of the line This system where the first person to arrive is the first to be served is a queue in real