T3474.字典序最小的生成字符串

greedy, string, https://leetcode.cn/problems/lexicographically-smallest-generated-string/

给你两个字符串，str1 和 str2，其长度分别为 n 和 m 。

如果一个长度为 n + m - 1 的字符串 word 的每个下标 0 <= i <= n - 1 都满足以下条件，则称其由 str1 和 str2 生成：

如果 str1[i] == 'T'，则长度为 m 的 子字符串（从下标 i 开始）与 str2 相等，即 word[i..(i + m - 1)] == str2。
如果 str1[i] == 'F'，则长度为 m 的 子字符串（从下标 i 开始）与 str2 不相等，即 word[i..(i + m - 1)] != str2。

返回可以由 str1 和 str2 生成的 字典序最小 的字符串。如果不存在满足条件的字符串，返回空字符串 ""。

如果字符串 a 在第一个不同字符的位置上比字符串 b 的对应字符在字母表中更靠前，则称字符串 a 的 字典序小于 字符串 b。如果前 min(a.length, b.length) 个字符都相同，则较短的字符串字典序更小。

子字符串 是字符串中的一个连续、非空的字符序列。

示例 1：

输入: str1 = "TFTF", str2 = "ab"

输出: "ababa"

解释:

下表展示了字符串 "ababa" 的生成过程：

下标	T/F	长度为 `m` 的子字符串
0	`'T'`	"ab"
1	`'F'`	"ba"
2	`'T'`	"ab"
3	`'F'`	"ba"

字符串 "ababa" 和 "ababb" 都可以由 str1 和 str2 生成。

返回 "ababa"，因为它的字典序更小。

示例 2：

输入: str1 = "TFTF", str2 = "abc"

输出: ""

解释:

无法生成满足条件的字符串。

示例 3：

输入: str1 = "F", str2 = "d"

输出: "a"

提示:

1 <= n == str1.length <= 10^4
1 <= m == str2.length <= 500
str1 仅由 'T' 或 'F' 组成。
str2 仅由小写英文字母组成。

要解决这个问题，我们需要构建一个长度为 $n + m - 1$ 的字符串，同时满足 str1 中所有的 'T'（子字符串必须等于 str2）和 'F'（子字符串不能等于 str2）约束，并确保结果是字典序最小的。

算法思路

填充固定字符：首先处理 str1 中所有的 'T'。如果 str1[i] == 'T'，则 word[i...i+m-1] 必须完全等于 str2。由于这些区间可能重叠，我们需要检查冲突：如果同一个位置被两个 'T' 要求设置为不同的字符，则无法生成字符串，直接返回 ""。
字典序最小初始化：为了使字典序最小，我们将所有未被 'T' 固定的位置初始填充为 'a'。
贪心处理 'F' 约束：依次检查 str1 中的 'F'。如果 str1[i] == 'F' 且当前的 word[i...i+m-1] 恰好等于 str2，我们必须修改该区间内的一个字符。
- 修改哪个字符？：为了保持字典序最小，我们应该修改下标尽可能靠后的字符（越靠后对字典序的影响越小）。
- 修改到什么？：由于该字符原本属于“非固定”位置（若是固定的则无法修改），初始为 'a' 且当前匹配了 str2，说明此时 str2 在该位置也是 'a'。我们将该字符递增（如变为 'b'），即可破坏匹配。
- 处理连锁反应：修改一个字符可能会导致之前已经检查过的 'F' 约束重新被违反。因此，一旦修改了某个位置 $k$ 的字符，我们需要将检查进度回退，重新验证受影响的窗口。
实现细节

使用 bytearray 来处理可变字符串。
使用 memoryview 进行高效的切片对比，避免不必要的内存拷贝。
通过 fixed 数组记录哪些位置是由 'T' 强制要求的，不能修改。

代码实现

python

class Solution:
    def generateString(self, str1: str, str2: str) -> str:
        n, m = len(str1), len(str2)
        L = n + m - 1
        str2_b = str2.encode()
        res = bytearray(L)  # 初始为 0
        fixed = [False] * L
        
        # 1. 处理 'T' 约束：填充固定字符并检查冲突
        for i in range(n):
            if str1[i] == 'T':
                for j in range(m):
                    char = str2_b[j]
                    if res[i+j] != 0 and res[i+j] != char:
                        return ""
                    res[i+j] = char
                    fixed[i+j] = True
        
        # 2. 将所有未确定的位置初始化为 'a'，以获得最小字典序
        for i in range(L):
            if res[i] == 0:
                res[i] = ord('a')
        
        # 3. 处理 'F' 约束
        mv = memoryview(res)
        i = 0
        while i < n:
            # 如果要求不相等但实际上相等了
            if str1[i] == 'F' and mv[i:i+m] == str2_b:
                # 寻找该窗口内最右侧的非固定字符进行修改
                k = -1
                for idx in range(i + m - 1, i - 1, -1):
                    if not fixed[idx]:
                        k = idx
                        break
                
                # 如果所有字符都是固定的且匹配了 str2，则无法满足 'F' 约束
                if k == -1:
                    return ""
                
                # 将该位置字符递增（'a' -> 'b' 等）
                # 由于原先匹配，res[k] 一定等于 str2_b[k-i]，递增后一定不再匹配
                if res[k] == ord('z'):
                    return ""  # 理论上 26 个字母足够，若超出则无解
                
                res[k] += 1
                
                # 修改 index k 后，可能会影响从 k-m+1 开始的窗口，回退指针重新检查
                i = max(0, k - m + 1)
            else:
                i += 1
            
        return res.decode()

复杂度分析

时间复杂度： $O (N \cdot M \cdot Σ)$ ，其中 $N$ 是 str1 长度， $M$ 是 str2 长度， $Σ = 26$ 是字符集大小。虽然有指针回退，但每个非固定位置最多被修改 25 次，且每次修改影响的范围有限。在 Python 中通过 memoryview 和 bytearray 的底层优化，该复杂度可以稳过。
空间复杂度： $O (N + M)$ ，用于存储结果字符串和固定标记数组。

计算机底层思维：
使用 bytearray 来处理可变字符串。从“字符串处理” → “字节数组操作（内存块）”。
使用 memoryview 进行高效的切片对比，避免不必要的内存拷贝。从“数据值” → “数据所在的位置（引用/视图）”。
位操作利用二进制本质。从“数值” → “二进制结构”
Dijkstra 的 Shunting Yard 算法（调度场算法）将表达式转换成计算机能够轻松、线性处理的后缀表达式。

T3474.字典序最小的生成字符串 ​

T3474.字典序最小的生成字符串