String Stamps

Moderate
0/80
Average time to solve is 15m
profile
Contributed by
7 upvotes
Asked in companies
AdobeUberBarclays

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]
Detailed explanation ( Input/output format, Notes, Images )
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
Sample Input 1:
2
6 4
aabcaa
abca
1 1
b
z
Sample Output 1:
0 2 1
-1
Explanation of Sample Input 1:
In test case 1, after the first stamp, 'S' = “abca##”.

After the second stamp, 'S' = “ababca”.

After the third test stamp, 'S' = “aabcaa”.

In test case 2, it is not possible to convert 'S' into 'TARGET'.
Sample Input 2:
2
3 2
Pqr
pq
2 2
mn
mn
Sample Output 2:
-1
0
Explanation of Sample Input 2:
In test case 1, it is not possible to convert 'S' into 'TARGET'.

In test case 2, after the first stamp, 'S' = “mn”.
Hint

Can we do all the stamps in reverse order to convert ‘TARGET’ into a string of all ‘#’?

Approaches (1)
Construction

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: 

 

  1. Declare ‘UNMATCHED’ set initialized to empty sets initially.
  2. Delcare ‘DONE’ vector inintialized to 0 initially.
  3. Declare stack ‘STACK’.
  4. Declare answer vector/list ‘ANS’ to store the answer.
  5. 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)
  6. 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:
            1. ‘DONE[j]’ = 1
            2. ‘STACK’.append('j')
  7. If all('DONE'):
    1. Reverse('ANS')
    2. Return ‘ANS’
  8. ELSE:
    1. Return [-1]
Time Complexity

O(N * M), Where ‘N’, ‘M’ is the size of the ‘TARGET’ and the size of the ‘STAMP’.

 

Since there are N indexes to process and it takes O(M) time to process a single index. Thus the time complexity will be O(N * M).

Space Complexity

O(N * M), Where ‘N’, ‘M’,  is the size of the ‘TARGET’ and the size of the ‘STAMP’.

 

Since space is required to store unmatched indexes for each substring. Thus the space complexity will be O(N * M).

Code Solution
(100% EXP penalty)
String Stamps
Full screen
Console