Lexicographically Smallest Generated String
You receive two strings, str1 and str2, of lengths n and m, respectively.
A string word of length n + m - 1 is defined to be generated by str1 and str2 if it satisfies the following conditions for each index 0 <= i <= n - 1:
-
If
str1[i] == 'T', the substring ofwordwith sizemstarting at indexiis equal tostr2, i.e.,word[i..(i + m - 1)] == str2. -
If
str1[i] == 'F', the substring ofwordwith sizemstarting at indexiis not equal tostr2, i.e.,word[i..(i + m - 1)] != str2.
Produce the lexicographically smallest possible string that can be generated by str1 and str2. If no string can be generated, produce an empty string "".
Input: str1 = "TFTF", str2 = "ab"
Output: "ababa"
Explanation: The table below represents the string "ababa"
| Index | T/F | Substring of length m |
|---|---|---|
| 0 | 'T' | "ab" |
| 1 | 'F' | "ba" |
| 2 | 'T' | "ab" |
| 3 | 'F' | "ba" |
The strings "ababa" and "ababb" can be generated by str1 and str2.
Produce "ababa" since it is the lexicographically smaller string.
Input: str1 = "TFTF", str2 = "abc"
Output: ""
Explanation: No string that satisfies the conditions can be generated.
Input: str1 = "F", str2 = "d"
Output: "a"
Constraints
1 <= n == str1.length <= 10^41 <= m == str2.length <= 500str1consists only of'T'or'F'.str2consists only of lowercase English characters.
Did this problem appear in one of your interviews?
Responses stay private.