lexi_smallest_gen_str.py (1636B)
| # 3474. 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'. if 'str1[i] == T' the substring of 'word' with
size 'm' starting at index 'i' is equal to 'str2', ie. 'word[i .. (i + m -
1)] == str2', and vice versa. return the lexicographically smallest possible
string that can be generated by 'str1' and 'str2'. if no string can be
generated, return an empty string.
"""
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)
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
for i, ch in enumerate(str1):
if ch == "F":
if any(str2[j - i] != s[j] for j in range(i, i + m)):
continue
for j in range(i + m - 1, i - 1, -1):
if not fixed[j]:
s[j] = "b"
break
else:
return ""
return "".join(s)
if __name__ == "__main__":
obj = Solution()
print(obj.generateString(str1="TFTF", str2="ab"))
print(obj.generateString(str1="TFTF", str2="abc"))
print(obj.generateString(str1="F", str2="d"))
|
