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

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Stamping The Sequence

Difficulty: Hard

Problem Description

You are given two strings stamp and target. Initially, there is a string s of length target.length with all s[i] == '?'. In one turn, you can place stamp over s and replace every letter in s with the corresponding letter from stamp. We want to convert s to target using at most 10 * target.length turns. Return an array of the index of the left-most letter being stamped at each turn. If we cannot obtain target from s within 10 * target.length turns, return an empty array.

Key Insights

  • We can only stamp stamp onto s if it is fully contained within the boundaries of s.
  • A turn can replace any ? in s with the corresponding character from stamp.
  • The goal is to determine the sequence of stamp operations needed to convert s to target.
  • We can use a greedy approach to replace segments of s with stamp as we match them with target.

Space and Time Complexity

Time Complexity: O(n * m), where n is the length of target and m is the length of stamp.
Space Complexity: O(n), for the result array and potentially for storing intermediate states.

Solution

To solve the problem, we can use a greedy algorithm that iteratively finds the leftmost position in s where stamp can be placed to match the target. We maintain a boolean array to track which parts of target have been stamped. We will continue this process until s matches target or we exhaust our turns. The main data structures used are a boolean array to mark matched characters and a list to store the indices of stamp operations.

Code Solutions

def movesToStamp(stamp: str, target: str) -> List[int]:
    m, n = len(stamp), len(target)
    s = ['?'] * n
    visited = [False] * n
    res = []
    
    def can_stamp(start):
        match = 0
        for i in range(m):
            if target[start + i] == stamp[i] or s[start + i] == '?':
                match += 1
        return match
    
    def do_stamp(start):
        for i in range(m):
            s[start + i] = stamp[i]
    
    while True:
        stamped = False
        for i in range(n - m + 1):
            if not visited[i] and can_stamp(i) == m:
                visited[i] = True
                do_stamp(i)
                res.append(i)
                stamped = True
        
        if all(v or s[i] == target[i] for i, v in enumerate(visited)):
            return res[::-1]

        if not stamped:
            break
            
    return []
← Back to All Questions