Editorial

Solution walkthrough

Review the explanation, then compare the reference implementation.

Video explanation

Solution

Intuition

A T window fixes every character it covers, so those requirements must be resolved first. Other positions should begin as a for lexicographic minimality. An F window needs only one mismatch; when it accidentally matches, place that mismatch as far right as the fixed positions allow.

Approach

Allocate the output with a characters and a parallel array marking fixed positions. For every T, copy str2 into its window. If overlapping fixed characters disagree, return an empty string immediately.

Then inspect F windows from left to right. Leave an already different window unchanged. If it equals str2, scan that window from right to left for a position not fixed by any T and set it to b. If no such position exists, the required mismatch is impossible, so return an empty string.

The rightmost repair preserves the longest possible lexicographically minimal prefix and can also satisfy overlapping later F windows. Fixed positions are never altered, so every required T occurrence is preserved. Return the joined character array after processing all constraints.

class Solution:
    def generateString(self, str1: str, str2: str) -> str:
        n, m = len(str1), len(str2)
        res = ['a'] * (n + m - 1)
        used = [False] * (n + m - 1)

        for i in range(n):
            if str1[i] == 'T':
                for j in range(i, i + m):
                    if used[j] and res[j] != str2[j - i]:
                        return ''
                    res[j] = str2[j - i]
                    used[j] = True

        for i in range(n):
            if str1[i] == 'F':
                if all(res[j] == str2[j - i] for j in range(i, i + m)):
                    mismatch = False
                    for j in range(i + m - 1, i - 1, -1):
                        if not used[j]:
                            res[j] = 'b'
                            mismatch = True
                            break
                    if not mismatch:
                        return ''

        return "".join(res)

Complexity analysis

Let n = str1.length and m = str2.length. Time: O(n * m). Auxiliary space: O(n + m) for the generated character array and fixed-position flags.