You are given 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:
str1[i] == 'T', the of word with size m starting at index i is equal to str2, i.e., word[i..(i + m - 1)] == str2.str1[i] == 'F', the of word with size m starting at index i is not equal to str2, i.e., word[i..(i + m - 1)] != str2.Return the possible string that can be generated by str1 and str2. If no string can be generated, return an empty string "".
Example 1:
Input: str1 = "TFTF", str2 = "ab"
Output: "ababa"
Explanation:
"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.
Return "ababa" since it is the lexicographically smaller string.
Example 2:
Input: str1 = "TFTF", str2 = "abc"
Output: ""
Explanation:
No string that satisfies the conditions can be generated.
Example 3:
Input: str1 = "F", str2 = "d"
Output: "a"
Constraints:
1 <= n == str1.length <= 1041 <= m == str2.length <= 500str1 consists only of 'T' or 'F'.str2 consists only of lowercase English characters.