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

Solution

All algorithms I know for this problem follow the same pattern: let us start from the end and try to go in opposite direction. Imagine, that we have target = aabcaca, stamp = abca. Then we can go back and create a????ca string, then we can go to a?????? and finally to ???????. So, let us explain algorithm step by step:

  1. Let m and n be length of stamp and target.
  2. Let masks be binary masks for every window, when we put stamp on target. There will be n - m + 1 possible places for window. Window have 0 on place if stamp and target have the same element in given place. That is if bitmask equal to 0, we have full occurrence of stamp inside target.
  3. Now, we create these masks and also create set visited of indexes (starts of windows) and queue with candidates.
  4. We always keep in our queue candidates, such that they fully coincide with part of target (if we have ? symbol, it can be chosen as any symbol). We extract new candidate from left of our queue and add it to answer.
  5. Now, we want to understand, which elements we need to update, that is put ? to them. We have target_mask variable for this.
  6. Let us iterate over each element we need to update (for example in a????ca -> a?????? we need to update last two elements) and when we mark element as ?, we need to update all bits in masks[j]. Also we update target_mask.
  7. Let us found masks which are equal to 0 and add them to our queue if they are not visited yet.
  8. Finally, if target_mask is equal to zero, we return reversed answer and empty list in opposite case.

Complexity

Time complexity for first step is O((n-m)* n): first, we need to create masks, then for each of n elements, which we mark with ?, we need to spend O(m) iterations to do it: they will change this number of windows. Also to_update can have potential size m, but we will put every of n elements to and out of queue only once. Finally, part, where we are looking for zero masks have also O(m) complexity and repeated no more than m times. Final time complexity is O(n^2). Space complexity is O(n(n-m)).

Remark

Note, that we use bitmask with big size (more than 32 or 64) here and python allow us to do it. Moreover, when we update masks, at the moment we use loops, if we replace it with direct update it potentially will be much faster, I will try to do it later.

Code

class Solution:
    def movesToStamp(self, stamp, target):
        m, n = len(stamp), len(target)
        masks = [(1<<m) - 1]*(n - m + 1)
        target_mask = (1<<n) - 1
        queue = deque()
        visited = set()
        for i in range(n - m + 1):
            for j in range(m):
                masks[i] ^= (1<<j)*(target[j+i] == stamp[j])
            if masks[i] == 0:
                visited.add(i)
                queue.append(i)
        
        ans = []
                
        while queue and target_mask != 0:
            cand = queue.popleft()
            ans.append(cand)
            to_update = [i for i in range(cand, min(n, cand + m)) if target_mask & (1<<i)]

            for i in to_update:
                for j in range(max(0, i - m + 1), min(i + 1, n - m + 1)):
                    masks[j] = masks[j] - (masks[j] & (1<<(i - j)))
                target_mask ^= (1<<i)

            for j in range(max(0, cand - m + 1), min(cand + m, n - m + 1)):
                if masks[j] == 0 and j not in visited:
                    visited.add(j)
                    queue.append(j)
        
        return ans[::-1] if target_mask == 0 else []

If you like the solution, you can upvote it on leetcode discussion section: Problem 0936