LeetCode 936 - Stamping The Sequence

https://leetcode.com/problems/stamping-the-sequence/

You want to form a target string of lowercase letters.

At the beginning, your sequence is target.length '?' marks.  You also have a stamp of lowercase letters.

On each turn, you may place the stamp over the sequence, and replace every letter in the sequence with the corresponding letter from the stamp.  You can make up to 10 * target.length turns.

For example, if the initial sequence is "?????", and your stamp is "abc",  then you may make "abc??", "?abc?", "??abc" in the first turn.  (Note that the stamp must be fully contained in the boundaries of the sequence in order to stamp.)

If the sequence is possible to stamp, then return an array of the index of the left-most letter being stamped at each turn.  If the sequence is not possible to stamp, return an empty array.

For example, if the sequence is "ababc", and the stamp is "abc", then we could return the answer [0, 2], corresponding to the moves "?????" -> "abc??" -> "ababc".

Also, if the sequence is possible to stamp, it is guaranteed it is possible to stamp within 10 * target.length moves.  Any answers specifying more than this number of moves will not be accepted.

Example 1:

Input: stamp = "abc", target = "ababc"
Output: [0,2]
([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]

Approach 1: Work Backwards

Imagine we stamped the sequence with moves $m_1, m_2, \cdots$. Now, from the final position target, we will make those moves in reverse order.

Let's call the ith window, a subarray of target of length stamp.length that starts at i. Each move at position i is possible if the ith window matches the stamp. After, every character in the window becomes a wildcard that can match any character in the stamp.

For example, say we have stamp = "abca" and target = "aabcaca". Working backwards, we will reverse stamp at window 1 to get "a????ca", then reverse stamp at window 3 to get "a??????", and finally reverse stamp at position 0 to get "???????".

Algorithm

Let's keep track of every window. We want to know how many cells initially match the stamp (our "made" list), and which ones don't (our "todo" list). Any windows that are ready (ie. have no todo list), get enqueued.

Specifically, we enqueue the positions of each character. (To save time, we enqueue by character, not by window.) This represents that the character is ready to turn into a "?" in our working target string.

Now, how to process characters in our queue? For each character, let's look at all the windows that intersect it, and update their todo lists. If any todo lists become empty in this manner (window.todo is empty), then we enqueue the characters in window.made that we haven't processed yet.

• Time Complexity: $O(N(N-M))$, where $M, N$ are the lengths of stamp, target.
• Space Complexity: $O(N(N-M))$. 

    public int[] movesToStamp(String stamp, String target) {

        int M = stamp.length(), N = target.length();

        Queue<Integer> queue = new ArrayDeque();

        boolean[] done = new boolean[N];

        Stack<Integer> ans = new Stack();

        List<Node> A = new ArrayList();

        for (int i = 0; i <= N-M; ++i) {

            // For each window [i, i+M), A[i] will contain

            // info on what needs to change before we can

            // reverse stamp at this window.

            Set<Integer> made = new HashSet();

            Set<Integer> todo = new HashSet();

            for (int j = 0; j < M; ++j) {

                if (target.charAt(i+j) == stamp.charAt(j))

                    made.add(i+j);

                else

                    todo.add(i+j);

            }

            A.add(new Node(made, todo));

            // If we can reverse stamp at i immediately,

            // enqueue letters from this window.

            if (todo.isEmpty()) {

                ans.push(i);

                for (int j = i; j < i + M; ++j) if (!done[j]) {

                    queue.add(j);

                    done[j] = true;

                }

            }

        }

        // For each enqueued letter (position),

        while (!queue.isEmpty()) {

            int i = queue.poll();

            // For each window that is potentially affected,

            // j: start of window

            for (int j = Math.max(0, i-M+1); j <= Math.min(N-M, i); ++j) {

                if (A.get(j).todo.contains(i)) {  // This window is affected

                    A.get(j).todo.remove(i);

                    if (A.get(j).todo.isEmpty()) {

                        ans.push(j);

                        for (int m: A.get(j).made) if (!done[m]) {

                            queue.add(m);

                            done[m] = true;

                        }

                    }

                }

            }

        }

        for (boolean b: done)

            if (!b) return new int[0];

        int[] ret = new int[ans.size()];

        int t = 0;

        while (!ans.isEmpty())

            ret[t++] = ans.pop();

        return ret;

    }

class Node {

    Set<Integer> made, todo;

    Node(Set<Integer> m, Set<Integer> t) {

        made = m;

        todo = t;

    }

}