3474. Lexicographically Smallest Generated String

3474. Lexicographically Smallest Generated String

Difficulty: Hard

Topics: Principal, String, Greedy, String Matching, Weekly Contest 439

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, 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"

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"

Example 4:

• Input: str1 = "bababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababaaa", str2 = "bab"
• Output: "babbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabaaa"

Example 5:

• Input: str1 = "TT", str2 = "ab"
• Output: "aba"
• Explanation: Overlapping T constraints merge correctly

Example 6:

• Input: str1 = "FF", str2 = "aa"
• Output: "aba"
• Explanation: Both substrings must not equal "aa"

Constraints:

• 1 <= n == str1.length <= 10⁴
• 1 <= m == str2.length <= 500
• str1 consists only of 'T' or 'F'.
• str2 consists only of lowercase English characters.

Hint:

1. Use dynamic programming.
2. Fill the fixed part.
3. Use KMP's next table for DP.
4. The state is the prefix length and the longest suffix length that matches the pattern.
5. Each unknown character can be selected from ['a', 'b'].
6. Can you think of a greedy approach?

Solution:

We must construct a string word of length n + m - 1. Each index i in str1 imposes a rule on the substring word[i..i+m-1]:

• 'T' → must equal str2
• 'F' → must not equal str2
  • To obtain the lexicographically smallest string, we:
  • First enforce all 'T' constraints.
  • Fill remaining characters with 'a'.
  • Then adjust positions to satisfy 'F' constraints by changing characters to 'b' if needed.
  • If at any step a constraint cannot be satisfied, return "".

Approach:

• Determine the final word length:
  • N = n + m - 1
• Create an array word initialized with placeholder characters.
• Process 'T' constraints:
  • Force substrings to match str2.
• Fill remaining unknown characters with 'a'.
• Track which characters are modifiable.
• Process 'F' constraints:
  • If a forbidden substring equals str2, modify the rightmost changeable character.
• Convert the character array to a string and return it.

Let's implement this solution in PHP: 3474. Lexicographically Smallest Generated String

<?php
/**
 * @param String $str1
 * @param String $str2
 * @return String
 */
function generateString(string $str1, string $str2): string
{
    ...
    ...
    ...
    /**
     * go to ./solution.php
     */
}

/**
 * @param $word
 * @param $str2
 * @param $i
 * @param $m
 * @return bool
 */
function isSame(&$word, $str2, $i, $m): bool
{
    ...
    ...
    ...
    /**
     * go to ./solution.php
     */
}

// Test cases
echo generateString("TFTF", "ab") . "\n";           // Output: "ababa"
echo generateString("TFTF", "abc") . "\n";          // Output: ""
echo generateString("F", "d") . "\n";               // Output: "a"
echo generateString("bababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababaaa", "bab") . "\n";               
// Output: echo generateString("bababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababaaa", "bab") . "\n";               // Output: "babbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabaaa"
echo generateString("TT", "ab") . "\n";               // Output: "aba"
echo generateString("FF", "aa") . "\n";               // Output: "aba"
?>

Explanation:

1. Determine Final Word Length
   • The constructed word must allow every index i in str1 to contain a substring of length m.
   • Therefore: N = n + m - 1
   • Example:

      n = 4
      m = 2
      N = 5

1. Initialize Word

   • Use placeholder $ for unknown characters.
   • Example: word = ['$','$','$','$','$']

2. Process 'T' Conditions

   • For every i where str1[i] == 'T': word[i .. i+m-1] = str2
   • If the position already contains a conflicting character → return "".
   • Example:

     str1 = TFTF
     str2 = ab
   

• After applying 'T':

      index 0 -> "ab"
      index 2 -> "ab"

      word = a b a b $

1. Fill Remaining Characters

   • To achieve the lexicographically smallest string, fill unused positions with 'a'. word = a b a b a
   • Also track which positions can still change.

2. Process 'F' Conditions

   • For each i where: str1[i] == 'F'
   • Check: word[i..i+m-1] == str2
   • If equal → we must break the match.
   • Strategy:
     • Change the rightmost changeable character inside the substring.
     • Replace 'a' with 'b'.
   • Why rightmost?
     • Keeps earlier characters smaller → preserves lexicographic minimality.

3. Edge Case

   • If the substring matches str2 but no character can be modified, then: return "" because the constraint cannot be satisfied.

Complexity

• Time Complexity:
  • Applying 'T' constraints → O(n * m)
  • Checking 'F' constraints → O(n * m)
  • Overall: O(n * m)
  • Where:
  • n ≤ 10⁴
  • m ≤ 500
  • Worst case ≈ 5 × 10⁶ operations.
• Space Complexity:
  • Word array: O(n + m)
  • Changeable flags: O(n + m)
  • Total: O(n + m)

Contact Links

If you found this series helpful, please consider giving the repository a star on GitHub or sharing the post on your favorite social networks 😍. Your support would mean a lot to me!

If you want more helpful content like this, feel free to follow me:

• LinkedIn
• GitHub

---

1. Substring: A substring is a contiguous non-empty sequence of characters within a string. ↩

2. Lexicographically Smaller: A string a is lexicographically smaller than a string b if in the first position where a and b differ, string a has a letter that appears earlier in the alphabet than the corresponding letter in b. If the first min(a.length, b.length) characters do not differ, then the shorter string is the lexicographically smaller one. ↩