Stamping The Sequence

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.

  • For example, if stamp = "abc" and target = "abcba", then s is "?????" initially. In one turn you can:
  • Place stamp at index 0 of s to obtain "abc??".
  • Place stamp at index 1 of s to obtain "?abc?".
  • Place stamp at index 2 of s to obtain "??abc".
  • Note that stamp must be fully contained in the boundaries of s in order to stamp; that is, you cannot place stamp at index 3 of s in the example above.

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.

Example 1
Inputstamp = "abc", target = "ababc"
Output[0,2]
Placing the stamp at index 0 produces "abc??", then placing it at index 2 produces "ababc"; other valid sequences may also be accepted.
Example 2
Inputstamp = "abca", target = "aabcaca"
Output[3,0,1]
Placing the stamp at indices 3, 0, and 1 transforms the initial question marks into "aabcaca".

Constraints

  • 1 <= stamp.length <= target.length <= 1000
  • stamp and target consist of lowercase English letters.

Asked at 1 companies

</>

Your Solution

(Ctrl/Cmd + Enter)

Switching Language

Loading template...

Loading...

Sign in to save your progress

AI code evaluation

Get a correctness verdict, missed edge cases, and complexity analysis of your solution.

Sign in to evaluate