3628. 插入一个字母的最大子序列数

发表于 分类于 阅读次数： Waline： 本文字数： 1.2k 阅读时长 ≈ 4 分钟

考点

  • 状态机DP
  • 前后缀分解

思路

题意

给定一个由大写字母组成的字符串 s，允许在任意位置插入至多一个大写字母，使最终字符串中子序列 “LCT” 的数量最大。子序列指按下标递增选取字符，不要求连续。

本讲义只关注字符 L、C、T；其余字符对计数无贡献，可忽略。

一、关键易错点：不能用“两层 DP（插入/不插入）+ 只保留一个最优态”来做

很多状态机 DP 会尝试维护两层状态：

  • 未插入：(L0, LC0, LCT0)
  • 已插入：(L1, LC1, LCT1)，并在遍历过程中只保留一个“最优”的已插入状态（例如优先最大化 LCT，再最大化 LC，再最大化 L）。

这在本题会导致错误，其根本原因是：

  • 插入 T 的收益只依赖前缀 LC；
  • 插入 L 的收益只依赖后缀 CT；
  • 插入 C 的收益依赖 前缀 L 的数量与后缀 T 的数量的乘积，即位置相关的 L_prefix × T_suffix。

已插入状态若只记录 (L, LC, LCT)，并在遍历中剪枝丢掉其它候选，会丢失“插入位置对应的后缀 T 数量”信息，导致后续无法达到最优。也就是说，该问题的“已插入一次”状态并不满足常见的支配剪枝条件，不能安全压缩成一个三元组最优态。

因此，本题的可靠结构是：

  1. 先用一次遍历计算原串中 LCT 的数量（记为 base）；
  2. 再分别计算插入 L、C、T 带来的 LCT 增量，取最大；
  3. 返回 base + 增量最大值。

二、插入 L / C / T 各自带来的增量

设插入位置为某个边界（插在某个字符之前）。只需比较三种插入选择的最优增量。

1）插入 T 的增量

把 T 插到最右边最优。新 T 可以与左侧所有子序列 “LC” 组合成新的 “LCT”。

  • 增量 = 全串中子序列 “LC” 的数量。
  • 记为 LC_total。

2）插入 L 的增量

把 L 插到最左边最优。新 L 可以与右侧所有子序列 “CT” 组合成新的 “LCT”。

  • 增量 = 全串中子序列 “CT” 的数量。
  • 记为 CT_total。

3）插入 C 的增量

若把 C 插在某个边界处，新产生的 “LCT” 必须由：

  • 左侧选一个 L；
  • 右侧选一个 T；

因此该边界的增量为：L_left * T_right，取所有边界的最大值即可

  • 记为 bestInsertC = max_over_boundaries(L_left * T_right)

三、LCT（原串 base）如何一次遍历得到

使用经典子序列计数状态机，维护三个变量：

  • l：当前前缀中 'L' 的数量（即子序列 “L” 的数量）
  • lc：当前前缀中子序列 “LC” 的数量
  • lct：当前前缀中子序列 “LCT” 的数量

从左到右扫描字符 ch：

  • 若 ch == 'L'：l += 1
  • 若 ch == 'C'：lc += l（每个已有的 L 都可与该 C 组成一个 LC）
  • 若 ch == 'T'：lct += lc（每个已有的 LC 都可与该 T 组成一个 LCT）
  • 其它字符：不变

扫描结束时，lct 即为原串 base。

四、一次扫描同时算出 base 与三种增量（对应 AC 代码）

下面代码以状态机方式在一次遍历中同时计算：

  • lct：原串 base
  • lc：LC_total（插 T 的增量）
  • ct：CT_total（插 L 的增量）
  • mx：bestInsertC（插 C 的增量）

其中 t 表示“尚未扫描到的后缀中 T 的数量”，用于实时计算 l * t 并取最大。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
class Solution {
public:
    long long numOfSubsequences(string s) {

        // t：当前仍位于“未扫描后缀”中的 'T' 数量（初始为全串 T 的数量）
        long long t = 0;
        for (char ch : s) {
            if (ch == 'T') ++t;
        }

        // 状态机变量
        long long l = 0;     // 前缀 L 数（子序列 "L" 数）
        long long c = 0;     // 前缀 C 数（用于统计 "CT"）
        long long lc = 0;    // 前缀子序列 "LC" 数（也是全串 LC_total）
        long long ct = 0;    // 前缀子序列 "CT" 数（扫完后即 CT_total）
        long long lct = 0;   // 前缀子序列 "LCT" 数（扫完后即 base）
        long long mx = 0;    // max(l * t)：插入 C 的最佳增量

        for (char ch : s) {

            // 1) 更新子序列计数状态机
            if (ch == 'L') {
                ++l;
            } else if (ch == 'C') {
                lc += l;     // 形成新的 "LC"
                ++c;         // 记录 C，用于将来遇到 T 形成 "CT"
            } else if (ch == 'T') {
                lct += lc;   // 形成新的 "LCT"
                ct  += c;    // 形成新的 "CT"
                --t;         // 越过一个 T，后缀剩余 T 数减少
            }

            // 2) 枚举“插入 C”的最优位置：取 max(前缀 L 数 * 后缀 T 数)
            // 此处 l 表示当前边界左侧 L 数，t 表示当前边界右侧剩余 T 数
            mx = max(mx, l * t);
        }

        // 三种插入增量取最大：插 L -> ct，插 T -> lc，插 C -> mx
        long long extra = max(mx, max(lc, ct));

        return lct + extra;
    }
};