936. Stamping The Sequence

Problem Description

Given two strings, stamp and target, we need to determine the sequence of indices where stamp should be placed on target to transform target into a string with all '?' characters. The stamp operation replaces characters in target with the corresponding characters from stamp. The solution must use at most 10 * target.length turns.

Solution Explanation: Reverse Thinking and Topological Sort

A forward approach is complex due to overwriting. Instead, we reverse the problem. We start from target and work backward towards a string of all '?'. This simplifies the process significantly.

The core idea is to identify places in target where placing the stamp will match part or all of the stamp. The algorithm works by iteratively applying the stamp in reverse and tracking changes until either target is fully transformed into a string of '?' or it's clear the transformation isn't possible.

Data Structures:

• indeg: An array that keeps track of how many characters in each possible stamp placement window differ from the stamp's characters. Initially, it’s the length of the stamp. If indeg[i] == 0, the ith window matches the stamp.
• g: An adjacency list to represent dependencies between different window positions. g[i] contains the list of windows that are affected if the ith position is replaced.
• q: A queue to manage windows ready to be stamped (those with indeg[i] == 0).
• vis: An array to mark visited positions in target to avoid redundant stamping.
• ans: An array to store the sequence of stamp placement indices.

Algorithm:

1. Initialization: Calculate indeg for all possible stamp positions. Populate g to show dependencies between positions. Push positions with indeg == 0 to q.

2. Topological Sort: While q is not empty:

   • Dequeue a position i from q.
   • Add i to ans.
   • Mark positions in target covered by the stamp at position i as visited using vis.
   • Update indeg for windows whose characters overlap with the newly stamped region. If a window's indeg becomes 0, add it to q.

3. Validation: Check if all positions are visited (vis). If yes, the transformation is possible, and ans (reversed) is the solution. Otherwise, return an empty array.

Code Implementation (Python)

from collections import deque
 
class Solution:
    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 []

Time and Space Complexity

• Time Complexity: O(n * (n - m + 1)), where n is the length of target and m is the length of stamp. This is because we iterate through all possible stamp positions and their overlapping regions.

• Space Complexity: O(n * (n - m + 1)) for indeg and g. Other arrays (vis, ans) are O(n).

The provided solution efficiently solves the problem using a clever reverse approach and a topological sort-like algorithm. The code is well-structured and uses appropriate data structures for optimal performance. The complexity analysis accurately reflects the algorithm's efficiency.