Last Updated: 22 Mar, 2021

String Stamps

Moderate

Asked in companies

Solve now

Problem statement

You are given two strings 'S', and 'TARGET' of length 'N', and a string 'STAMP' of length 'M'. 'S' is initially made up of only character ‘#’. Your goal is to convert 'S' into 'TARGET' by stamping 'S' with 'STAMP' no more than 5 * 'N' times.

Stamping means takes a substring of 'S' of length 'M' and replace it with 'STAMP'.

Return the sequence of moves to convert 'S' into 'TARGET'. Each move represents the starting index of the substring we want to replace. If it is not possible to convert 'S' into 'TARGET' return an array containing only one element -1.

For example:

'S'= “#####” 'TARGET' = “ababbb” 'STAMP' = “ab”
Stamping substring starting at 4 , 'S' = “####ab”
Stamping substring starting at 3 , 'S' = “###abb”
Stamping substring starting at 2 , 'S' = “##abbb”  
Stamping substring starting at 0 , 'S' = “ababbb”

Answer = [4, 3, 2, 0]

Input Format:

The first line of input contains an integer T’ denoting the number of test cases to run.

The first line of each test case contains two space-separated integers ‘N’ and ‘M’ denoting the length of 'TARGET' and 'STAMP' respectively.

The second line of each test case contains the string 'TARGET'.

The third line of each test case contains the string 'STAMP'.

Output Format:

For each test case, return the moves of size not greater than 5 * 'N', to convert 'S' into 'TARGET'.

Output for each test case is printed in a separate line.

Note:

You don’t need to print anything. It has already been taken care of. Just implement the given function.

Constraints:

1 <= T <= 5
1 <= N, M <= 1000 
M <= N

TARGET and stamp have only lower case English characters.

Time Limit: 1 sec

Solve now

Approaches

01 Approach

We will do the process in reverse. We will iterate over the substrings of ‘TARGET’ and try to convert them into ‘#’. Two characters of ‘TARGET’ and ‘STAMP’ matches if they are equal or the character in ‘TARGET’ is already replaced with a ‘#’.

We will maintain an array of indexes for each substring starting at ‘i’ which are not matching with character in ‘STAMP’. If some substring matches with ‘STAMP’ we will insert all its indexes in ‘STACK’.

We will pop an index from the ‘STACK’ and remove it from all the UNMATCHED array that contains it. If any of the UNMATCHED arrays becomes empty we will push it to the STACK and repeat the process.

The steps are as follows:

Declare ‘UNMATCHED’ set initialized to empty sets initially.
Delcare ‘DONE’ vector inintialized to 0 initially.
Declare stack ‘STACK’.
Declare answer vector/list ‘ANS’ to store the answer.
For ‘i’ in range('N' - ‘M’ + 1):
- For ‘j’ in range('M'):
  - If ‘TARGET’[i+j] != ‘STAMP[j]’
    - ‘UNMATCHED[i]’.append('i' + ‘j’)
- If 'UNMATCHED[i]'.size()==0:
  1. ‘ANS’.append(i)
  2. For ‘j’ in range('i', ‘i’ + ‘M’):
    1. If ‘DONE[j]' == 0:
      1. ‘DONE’[j]=1
      2. ‘STACK’.append(j)
While len('STACK'):
1. ‘IDX’ = ‘STACK’.pop()
2. For ‘i’ in range(max(0, ‘IDX’ - ‘M’ + 1), ‘IDX’ + 1):
  1. If ‘UNMATCHED[i]’.size()==0
    1. continue
  2. ‘UNMATCHED[i]’.remove('IDX')
  3. If ‘UNMATCHED[i]’.size()==0:
    1. ‘ANS’.append('i')
    2. For 'j' in range('i', 'i' + ‘M’):
      1. If ‘DONE[j]’ == 0:
        ‘DONE[j]’ = 1
        ‘STACK’.append('j')
If all('DONE'):
1. Reverse('ANS')
2. Return ‘ANS’
ELSE:
1. Return [-1]

Solve now