You are given two strings, str1 of length n and str2 of length m.

A string word of length $n + m - 1$ is generated such that for each index i from $0$ to $n - 1$:

• If str1[i] == 'T', the substring of length m starting at index i, word[i .. i + m - 1], is equal to str2.

• If str1[i] == 'F', the substring of length m starting at index i, word[i .. i + m - 1], is not equal to str2.

Return the lexicographically smallest string word that can be generated. If no such string satisfies the conditions, return an empty string "".

Constraints:

• $1 \leq n =$ str1.length $\leq 10^4$

• $1 \leq m =$ str2.length $\leq 500$

• str1 consists only of 'T' and 'F'.

• str2 consists only of lowercase English letters.

Now, let’s take a moment to make sure you’ve correctly understood the problem. The quiz below helps you check if you’re solving the correct problem:

We have a game for you to play. Rearrange the logical building blocks to develop a clearer understanding of how to solve this problem.

Implement your solution in the following coding playground.