FastPrep

Description

Solutions

Generate Lexicographically Smallest String

📚RELATED PROBLEMS

String S1 of length L1 consisting of uppercase alphabets only. String S2 of length L2 consisting of characters 'T' and 'F' only. Generate a lexicographically smallest string S of length (L1 + L2 - 1) such that a substring of length L1 in string S starting at index (0 <= i < L2) is equal to S1 if and only if ith element of S2 is 'T'. If generating a string is not possible return -1.

Example 1:

Input:  S1 = "ABCA", S2 = "TFFF"
Output: "ABCAAAA" 
Explanation:
      
      S="ABCAAAA" is lexicographically smallest string that satisfies the given condition:-
      
      
        Character at index 0 of S2 = 'T' and Substring starting at index 0: "ABCA" is equal to S1.
        Character at index 1 of S2 = 'F'
        Character at index 2 of S2 = 'F'
        Character at index 3 of S2 = 'F'

Example 2:

Input:  S1 = "ABA", S2 = "TFT"
Output: "ABABA" 
Explanation:
      
      S="ABABA" is the lexicographically smallest string that satisfies the given condition.

Example 3:

Input:  S1 = "ABC", S2 = "TFT"
Output: "-1" 
Explanation:
      
      It is not possible to generate a string that satisfies the given condition, hence the output is -1.

Constraints:

1 <= L1 <= 10^4
1 <= L2 <= 100