3770 Lexicographically Smallest Generated String
Lexicographically Smallest Generated String 
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:
1
2
If str1[i] == 'T', the **substring** of word with size m starting at index i is **equal** to str2, i.e., word[i..(i + m - 1)] == str2.
If str1[i] == 'F', the **substring** of word with size m starting at index i is **not equal** to str2, i.e., word[i..(i + m - 1)] != str2.
Return the lexicographically smallest 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:
The table below represents the string “ababa”
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
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
2
3
4
1 <= n == str1.length <= 104
1 <= m == str2.length <= 500
str1 consists only of 'T' or 'F'.
str2 consists only of lowercase English characters.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
class Solution:
def generateString(self, str1: str, str2: str) -> str:
n, m = len(str1), len(str2)
s = ["a"] * (n + m - 1)
fixed = [False] * (n + m - 1)
# process the case of 'T'
for i, ch in enumerate(str1):
if ch == "T":
for j, c in enumerate(str2, i):
if fixed[j] and s[j] != c:
return ""
s[j], fixed[j] = c, True
# process the case of 'F'
for i, ch in enumerate(str1):
if ch == "F":
# check if there are already different characters
if any(str2[j - i] != s[j] for j in range(i, i + m)):
continue
# find the first modifiable position
for j in range(i + m - 1, i - 1, -1):
if not fixed[j]:
s[j] = "b"
break
else:
return ""
return "".join(s)