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:
Return the lexicographically smallest possible string that can be generated by str1 and str2. If no string can be generated, return an empty string "".
Examples
Example 1
Input: str1 = "TFTF", str2 = "ab"
Output: "ababa"
Explanation:
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 <= 104
1 <= m == str2.length <= 500
str1 consists only of 'T' or 'F'.
str2 consists only of lowercase English characters.
3474. Lexicographically Smallest Generated String
Hard
50 Points
String
Greedy
String Matching
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:
Return the lexicographically smallest possible string that can be generated by str1 and str2. If no string can be generated, return an empty string "".
Examples
Example 1
Input: str1 = "TFTF", str2 = "ab"
Output: "ababa"
Explanation:
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 <= 104
1 <= m == str2.length <= 500
str1 consists only of 'T' or 'F'.
str2 consists only of lowercase English characters.
Lexicographically Smallest Generated String - Practice Coding | SlaveCode