936. Stamping The Sequence

HardStackGreedyQueueString
Leetcode Link

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 the stamp could fit (each window being the length of the stamp).
  • We determine how many characters within each window do not match the stamp (using the in-degree array indeg).
  • 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 of 0).
  • We maintain an array vis to mark whether we've successfully stamped that portion of the target.
  • 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.

Learn more about Stack, Greedy and Queue patterns.

Not Sure What to Study? Take the 2-min Quiz to Find Your Missing Piece๏ผš

In a binary min heap, the maximum element can be found in:

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:

  1. In-degree array indeg: This array tracks the differences between the stamp and each window of the target. A window is a substring of target that has the same length as stamp. When indeg[i] is zero, it means the ith window matches the stamp perfectly, and we can consider "unstamping" from this point.

  2. Adjacency list g: This list represents the dependencies between different windows and the positions in the target string. Specifically, g[i] holds a list of window starts where the characters at position i in target don't match the stamp. So if we change the ith character in target, we need to update these windows.

  3. 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 the stamp.

  4. Visited array vis: This boolean array keeps track of whether each character has been covered by the "unstamping" process.

  5. Answer list ans: This list captures the sequence of positions where the stamp was used during the reverse process.

Algorithm:

  1. Initialization:

    • Set each entry of indeg to the length of the stamp, 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 the stamp. If they don't match, add the window's start position to g[i].

  2. 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] is False), mark vis[i + j] as True.
    • 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 the stamp).
    • 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."

  3. 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 build target from a string of question marks.
    • If there are positions that we did not visit, it means the target string cannot be covered by the stamp within the constraints, and we return an empty list.

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.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

What's the output of running the following function using input [30, 20, 10, 100, 33, 12]?

1def fun(arr: List[int]) -> List[int]:
2    import heapq
3    heapq.heapify(arr)
4    res = []
5    for i in range(3):
6        res.append(heapq.heappop(arr))
7    return res
8
1public static int[] fun(int[] arr) {
2    int[] res = new int[3];
3    PriorityQueue<Integer> heap = new PriorityQueue<>();
4    for (int i = 0; i < arr.length; i++) {
5        heap.add(arr[i]);
6    }
7    for (int i = 0; i < 3; i++) {
8        res[i] = heap.poll();
9    }
10    return res;
11}
12
1class HeapItem {
2    constructor(item, priority = item) {
3        this.item = item;
4        this.priority = priority;
5    }
6}
7
8class MinHeap {
9    constructor() {
10        this.heap = [];
11    }
12
13    push(node) {
14        // insert the new node at the end of the heap array
15        this.heap.push(node);
16        // find the correct position for the new node
17        this.bubble_up();
18    }
19
20    bubble_up() {
21        let index = this.heap.length - 1;
22
23        while (index > 0) {
24            const element = this.heap[index];
25            const parentIndex = Math.floor((index - 1) / 2);
26            const parent = this.heap[parentIndex];
27
28            if (parent.priority <= element.priority) break;
29            // if the parent is bigger than the child then swap the parent and child
30            this.heap[index] = parent;
31            this.heap[parentIndex] = element;
32            index = parentIndex;
33        }
34    }
35
36    pop() {
37        const min = this.heap[0];
38        this.heap[0] = this.heap[this.size() - 1];
39        this.heap.pop();
40        this.bubble_down();
41        return min;
42    }
43
44    bubble_down() {
45        let index = 0;
46        let min = index;
47        const n = this.heap.length;
48
49        while (index < n) {
50            const left = 2 * index + 1;
51            const right = left + 1;
52
53            if (left < n && this.heap[left].priority < this.heap[min].priority) {
54                min = left;
55            }
56            if (right < n && this.heap[right].priority < this.heap[min].priority) {
57                min = right;
58            }
59            if (min === index) break;
60            [this.heap[min], this.heap[index]] = [this.heap[index], this.heap[min]];
61            index = min;
62        }
63    }
64
65    peek() {
66        return this.heap[0];
67    }
68
69    size() {
70        return this.heap.length;
71    }
72}
73
74function fun(arr) {
75    const heap = new MinHeap();
76    for (const x of arr) {
77        heap.push(new HeapItem(x));
78    }
79    const res = [];
80    for (let i = 0; i < 3; i++) {
81        res.push(heap.pop().item);
82    }
83    return res;
84}
85

Example 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".

  1. 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.

  2. Building adjacency list (g) and initializing indeg:

    • We compare substrings (or windows) of target with stamp:
      • Window "aba" (from position 0 to 2) has 2 characters matching with stamp "abc", hence indeg[0] = 1.
      • Window "bab" (from position 1 to 3) has 0 characters matching with stamp "abc", hence indeg[1] = 3.
      • Window "abc" (from position 2 to 4) is a perfect match, hence indeg[2] = 0.
    • Update g: For window "aba", we will add 0 to g[1] because if the second character ('b') changes, the window will be affected.

  3. 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 to ans (so now ans = [2]).
    • We mark all vis positions within this window as 'True', so vis 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 the stamp due to "unstamping").

  4. 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 check g[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 matches stamp after "unstamping" "abc".
    • Again, we remove the front of the queue (0), append it to ans (so now ans = [2, 0]), and mark all of its vis positions as True.

  5. Final check and output:

    • Now vis is [True, True, True, True, True], which means every character in target has been "unstamped".
    • When reversed, ans becomes [0, 2]. This is the sequence of stamp placements in reverse; to build target from the string of question marks, we stamp at index 0 first and then at index 2.

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
Not Sure What to Study? Take the 2-min Quiz๏ผš

Which two pointer technique does Quick Sort use?

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.

Fast Track Your Learning with Our Quick Skills Quiz:

Problem: Given a list of tasks and a list of requirements, compute a sequence of tasks that can be performed, such that we complete every task once while satisfying all the requirements.

Which of the following method should we use to solve this problem?

Recommended Readings

Stack Intro

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

Greedy Introduction iframe width 560 height 315 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 When do we use greedy Greedy algorithms tend to solve optimization problems Typically they will ask you

Queue Intro

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

Got a question?ย Ask the Teaching Assistantย anything you don't understand.

Still not clear? Ask in the Forum, ย Discordย orย Submitย the part you don't understand to our editors.

โ†
โ†‘TA ๐Ÿ‘จโ€๐Ÿซ