Description
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 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.
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"
| 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 <= 500str1consists only of'T'or'F'.str2consists only of lowercase English characters.
Solutions
Sets the character to 'b' immediately upon finding the rightmost unfixed position and continues to the next 'F' constraint, returning empty string only if no unfixed position exists; this interleaves the modification with the search rather than separating validation and mutation.
/**
* @param {string} str1
* @param {string} str2
* @return {string}
*/
var generateString = function (str1, str2) {
const n = str1.length;
const m = str2.length;
const len = n + m - 1;
const dp = new Array(len).fill('a');
const fixed = new Array(len).fill(0);
for (let i = 0; i < n; i++) {
if (str1[i] === 'T') {
for (let j = i; j < i + m; j++) {
if (fixed[j] === 1 && dp[j] !== str2[j - i]) {
return '';
}
dp[j] = str2[j - i];
fixed[j] = 1;
}
}
}
outer_loop: for (let i = 0; i < n; i++) {
if (str1[i] === 'F') {
for (let j = i; j < i + m; j++) {
if (dp[j] !== str2[j - i]) {
continue outer_loop;
}
}
for (let j = i + m - 1; j >= i; j--) {
if (fixed[j] === 0) {
dp[j] = 'b';
continue outer_loop;
}
}
return '';
}
}
return dp.join('');
};