3474. Lexicographically Smallest Generated String

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 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 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:

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 <= 104
• 1 <= m == str2.length <= 500
• str1 consists only of 'T' or 'F'.
• str2 consists only of lowercase English characters.

 

Solutions

Solution: Greedy

• Time complexity: O(mn)
• Space complexity: O(mn)

 

JavaScript

/**
 * @param {string} str1
 * @param {string} str2
 * @return {string}
 */
const generateString = function (str1, str2) {
  const n = str1.length;
  const m = str2.length;
  const chars = Array.from({ length: n + m - 1 }, () => 'a');
  const fixed = Array.from({ length: n + m - 1 }, () => false);

  for (let a = 0; a < n; a++) {
    if (str1[a] !== 'T') continue;

    for (let b = a; b < a + m; b++) {
      const target = str2[b - a];

      if (target !== chars[b] && fixed[b]) return '';

      fixed[b] = true;
      chars[b] = target;
    }
  }

  for (let a = 0; a < n; a++) {
    if (str1[a] !== 'F') continue;

    let isValid = false;
    let index = -1;

    for (let b = a + m - 1; b >= a; b--) {
      const target = str2[b - a];

      if (target !== chars[b]) {
        isValid = true;
        break;
      }

      if (index === -1 && !fixed[b]) {
        index = b;
      }
    }

    if (isValid) continue;

    if (index === -1) return '';

    fixed[index] = true;
    chars[index] = 'b';
  }

  return chars.join('');
};