2370. 最长理想子序列

发表于 分类于 阅读次数： Waline： 本文字数： 817 阅读时长 ≈ 3 分钟

考点

  • 线性DP

思路

一、问题描述（Problem Restatement）

给定一个字符串 s（仅包含小写字母 'a' 到 'z'）和一个整数 k。

定义一个子序列是 理想的（ideal），当且仅当子序列中任意相邻两个字符 c1 和 c2 满足： \[ |c1 - c2| \le k \] 其中字符之间的差值按照字母表顺序计算（例如'a' → 0, 'b' → 1, 'c' → 2, … , 'z' → 25）。

目标：求 s 的最长理想子序列的长度。

二、问题建模（Modeling）

1. 子序列的特点

  • 子序列不要求连续
  • 顺序必须与原字符串一致
  • 是否能接在一起，只与 相邻字符的字母差 有关

这类问题的典型特征是：

  • 顺序相关
  • 状态具有“前缀最优性”

因此，适合使用 动态规划（Dynamic Programming）。

2. 状态定义（State Definition）

定义状态数组： \[ f[c] = \text{当前已处理前缀中，以字符 } c \text{ 结尾的最长理想子序列长度} \] 其中：

  • \(c \in [0, 25]\)，表示字符 'a' + c
  • f 的大小固定为 26，与字符串长度无关

三、状态转移方程（State Transition）

1. 当前字符的处理

设当前遍历到的字符为 s[i]，其对应的字母编号为： \[ x = s[i] - 'a' \] 如果要让 s[i] 成为子序列的最后一个字符，那么它可以接在所有满足条件的字符后面。

2. 可转移的前驱状态

根据题意，相邻字符需满足： \[ |x - j| \le k \] 因此，所有满足上述条件的 f[j] 都可以转移到 f[x]。

3. 转移公式

\[ f[x] = \max_{|x - j| \le k} (f[j] + 1) \]

同时，也要考虑 只包含当前字符自身的子序列： \[ f[x] \ge 1 \] 综合起来： \[ f[x] = \max \left(1,\ \max_{|x - j| \le k} (f[j] + 1)\right) \]

四、初始化与答案

1. 初始化

  • 初始时尚未处理任何字符
  • 所有 f[c] = 0

2. 最终答案

任意字符都可以作为最长理想子序列的结尾，因此答案为： \[ \text{ans} = \max_{c \in [0,25]} f[c] \]

五、复杂度分析（Complexity Analysis）

  • 状态数：26
  • 每个字符遍历 26 个可能的前驱字符

时间复杂度： \[ O(26 \times |s|) = O(|s|) \] 空间复杂度： \[ O(26) = O(1) \]

六、算法思想总结

  • 使用 字符结尾 DP，而非按下标建模
  • 将“相邻字符约束”直接体现在状态转移中
  • 利用字符集规模小（26）的特性，实现线性时间算法
  • 是“LIS + 约束条件”的典型变体

七、AC代码

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
class Solution {
public:
    int longestIdealString(string s, int k) {
        // f[c] 表示：以字符 ('a' + c) 结尾的最长理想子序列长度
        int f[26] = {};

        // 遍历字符串中的每一个字符
        for (char c : s) {
            int i = c - 'a';  // 当前字符对应的编号 [0, 25]

            // 至少可以只选当前字符本身，长度为 1
            int mx = 1;

            // 枚举所有可能作为前驱的字符
            for (int j = 0; j < 26; ++j) {
                // 若字符差不超过 k，则可以从 f[j] 转移
                if (abs(j - i) <= k) {
                    mx = max(mx, f[j] + 1);
                }
            }

            // 更新以字符 i 结尾的最优解
            f[i] = mx;
        }

        // 所有字符结尾状态中的最大值即为答案
        int res = 0;
        for (int i = 0; i < 26; ++i)
            res = max(res, f[i]);

        return res;
    }
};