We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Stamping The Sequence

Number: 973

Difficulty: Hard

Paid? No

Companies: Morgan Stanley

Problem Description

Given two strings, stamp and target, the goal is to transform an initial string s (of the same length as target and consisting entirely of '?' characters) into the target string. You are allowed to stamp over s with the stamp string. In one stamping move, you place stamp such that it is fully within s, and you replace the characters in s at that position with the corresponding characters from stamp. The twist is that some positions in s may already have a letter which needs to match the corresponding letter in stamp, or it may be a '?'. The challenge is to determine a sequence of stamping moves (by outputting the leftmost index each time) such that after all moves, the string s becomes the target, and the total number of moves is at most 10 * target.length. If no such sequence exists, return an empty array.

Key Insights

  • Reverse Process: Instead of simulating the stamping process from an empty string to the target, we reverse the process by "unstamping" the target. This helps to avoid branching paths due to overlapping stamps.
  • Greedy Approach: We try to find every possible window in the target that can be "cleaned" (i.e., turned into all '?' characters). Once cleaned, that window may help enable neighboring windows.
  • Recording Moves: Record the positions where unstamping happens. At the end, reverse the order of moves to get the correct stamping sequence.
  • Use of Data Structures: A queue (or list used as a queue) is used to process indices where a valid unstamping move is found; a boolean array is used to keep track of which windows have been visited.

Space and Time Complexity

Time Complexity: O(n * m) where n is the length of target and m is the length of stamp. In the worst-case, each window may be examined several times but overall is limited by n * m. Space Complexity: O(n + m) due to the additional arrays/queues used for bookkeeping.

Solution

The solution employs a greedy reverse approach:

  1. Convert the target string to a list (for easier modifications).
  2. For every possible starting index in target where stamp could be placed, check if by "unstamping" (turning letters into '?') the window is valid. A window is valid if for every letter it either already is a '?' or matches the corresponding letter in stamp.
  3. Use a queue to keep track of windows that are “unstampable”. For each window, once removed (i.e. replaced by '?'), update its neighboring windows because the '?' characters might cause those windows to become unstampable.
  4. Record the index for each unstamping move, and then reverse the order of moves at the end to obtain the stamping sequence.
  5. If after processing, the entire target is not turned into '?', return an empty array.

Key tricks include using an array of booleans to mark windows already processed and ensuring that even if a letter is a '?' (i.e., previously stamped), it is considered as matching in future comparisons.

Code Solutions

# Python solution for Stamping The Sequence

def movesToStamp(stamp: str, target: str):
    m, n = len(stamp), len(target)
    target_arr = list(target)
    # To mark if a window is processed
    done = [False] * (n - m + 1)
    res = []
    total_stamped = 0

    # For each window record the set of indices that are not yet '?'
    windows = []
    for i in range(n - m + 1):
        made, todo = set(), set()
        for j in range(m):
            if target_arr[i + j] == stamp[j]:
                made.add(i + j)
            else:
                todo.add(i + j)
        windows.append((made, todo))

    # Queue to hold indices of windows that are eligible for stamping (unstamping in reverse)
    queue = []
    for i, (made, todo) in enumerate(windows):
        if not todo:
            queue.append(i)
            done[i] = True

    while queue:
        i = queue.pop(0)
        # When we apply the stamp in reverse, mark all characters in that window as '?'
        made, todo = windows[i]
        # Only count updates for positions that haven't been stamped yet
        for j in list(made):
            if target_arr[j] != '?':
                target_arr[j] = '?'
                total_stamped += 1
                # Check all windows that might be affected by this position
                for k in range(max(0, j - m + 1), min(n - m, j) + 1):
                    if not done[k]:
                        # For window k, if position j was needed, remove it from todo
                        if j in windows[k][1]:
                            windows[k][1].remove(j)
                            if not windows[k][1]:
                                queue.append(k)
                                done[k] = True
        # Record this stamping move
        res.append(i)
    
    if total_stamped != n:
        # Not all characters turned into '?'
        return []
    # Reverse the sequence to get the stamping order
    return res[::-1]

# Example usage:
# print(movesToStamp("abc", "ababc"))
← Back to All Questions