区间动态规划例题：最小窗口子序列问题

题目描述
给定字符串 S 和 T，找出 S 中最短的连续子串，使得 T 是该子串的子序列。如果不存在这样的子串，返回空字符串。例如：

• S = "abcdebdde", T = "bde"，返回 "bcde"（最短满足条件的子串是 "bcde"，其中 T 是子序列）。
• S = "jmeqksfrsdcmsiwvaovztaqenprpvnbstl", T = "u"，返回 ""（不存在包含 u 的子串）。

解题思路
本题可通过动态规划记录匹配状态，利用“最后出现位置”来优化查找最小窗口。我们定义 dp[i][j] 表示 T 的前 j 个字符是 S 的前 i 个字符的子序列时，该子序列的起始位置。通过填充 dp 表，可快速定位所有有效窗口并选择最短的一个。

步骤详解

1. 状态定义

   • 设 dp[i][j] 表示：对于 S 的前 i 个字符和 T 的前 j 个字符，使得 T[1..j] 是 S[1..i] 的子序列的最长后缀子串的起始下标（下标从 1 开始）。
   • 若不存在这样的子序列，dp[i][j] = -1。

2. 初始化

   • 当 j = 0 时，T 为空串，任意 S 的前缀都包含空串，但我们需要记录起始位置。约定空串匹配的起始位置为 i+1（表示窗口长度为 0），但为方便计算，可设 dp[i][0] = i+1。
   • 当 i = 0 且 j > 0 时，S 为空，无法匹配非空 T，设 dp[0][j] = -1。

3. 状态转移方程

   • 若 S[i-1] == T[j-1]（字符匹配）：
     • 如果 j == 1，当前字符直接匹配，起始位置为 i。
     • 否则，起始位置继承自 dp[i-1][j-1]（即前一个匹配状态）。
   • 若 S[i-1] != T[j-1]：
     • 当前字符不匹配，起始位置继承自 dp[i-1][j]（在 S 的前 i-1 字符中匹配 T 的前 j 字符）。
   • 综合转移方程：

     if j == 0:
         dp[i][j] = i+1
     else if i == 0:
         dp[i][j] = -1
     else if S[i-1] == T[j-1]:
         if j == 1:
             dp[i][j] = i
         else:
             dp[i][j] = dp[i-1][j-1]
     else:
         dp[i][j] = dp[i-1][j]
     

4. 查找最小窗口

   • 遍历 i 从 1 到 len(S)，当 dp[i][len(T)] != -1 时，计算窗口长度 i - dp[i][len(T)] + 1。
   • 记录全局最小长度及对应的子串起始位置 dp[i][len(T)] 和结束位置 i。

5. 复杂度分析

   • 时间复杂度：O(n·m)，其中 n 和 m 分别为 S 和 T 的长度。
   • 空间复杂度：可优化至 O(m)（仅保留前一行的 dp 值）。

示例演示
以 S = "abcdebdde", T = "bde" 为例：

• 构建 dp 表（略去详细计算过程），最终在 i=5 时得到起始位置 2（对应子串 "bcde"），长度为 4；在 i=9 时得到起始位置 6（对应子串 "bdde"），长度为 4。两者均为最短，任选其一即可。

关键点

• 通过记录起始位置，避免暴力枚举所有子串。
• 状态转移时优先保证匹配的连续性，确保 T 是子序列。