2606. 找到最大开销的子字符串

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

考点

  • 线性DP
  • 最大子数组和

思路

一、问题概述

给定一个字符串 \(s\)，以及一个字符集合 chars 和对应的整数数组 vals，定义如下规则：

  • 若字符 \(c \in \texttt{chars}\)，则其权值为 vals 中对应的值；

  • 若字符 \(c \notin \texttt{chars}\)，则其权值默认为 \[ w(c) = c - \texttt{'a'} + 1 \]

目标是： 在字符串 \(s\) 的所有连续子串中，找到一个子串，使其字符权值之和最大，并返回该最大值。 允许选择空子串，因此答案下界为 \(0\)。

二、问题建模

1. 数值化建模

该问题的关键在于，将字符串问题转化为数组问题。

  • 对字符串 \(s\) 中的每个字符 \(s[i]\)，定义其权值为一个整数 \(a[i]\)；
  • 问题等价于： 在整数数组 \(a\) 中，求最大子数组和（Maximum Subarray Sum）。

这是一个经典的一维动态规划问题，可直接应用 Kadane 算法。

2. 权值映射的设计

由于字符范围仅为 'a' 到 'z'，可以使用一个长度为 26 的数组 w 进行权值映射：

  • 初始化时，令 \[ w[i] = i + 1 \quad (0 \le i < 26) \]

  • 对于 chars 中出现的字符，覆盖其默认权值： \[ w[\texttt{chars}[k] - 'a'] = \texttt{vals}[k] \]

这样即可在 \(O(1)\) 时间内获取任意字符的权值。

三、动态规划思想

1. 状态定义

设：

  • pre_v：以当前位置结尾的最大子串权值和
  • mx：全局最大子串权值和

2. 状态转移方程

对于当前位置字符的权值 \(v\)，有两种选择：

  1. 从当前位置重新开始一个子串；
  2. 将当前位置接在之前的最优子串之后。

因此状态转移为： \[ \text{pre\_v} = \max(v,\; v + \text{pre\_v}) \] 同时更新全局最优解： \[ \text{mx} = \max(\text{mx},\; \text{pre\_v}) \]

3. 初始化细节

  • 初始时从第一个字符开始： \[ \text{pre\_v} = w[s[0]] \]

  • 由于允许空子串，答案至少为 \(0\)，因此： \[ \text{mx} = \max(0,\; \text{pre\_v}) \]

四、算法流程总结

  1. 构建字符到权值的映射数组 w；
  2. 使用 Kadane 算法遍历字符串；
  3. 在遍历过程中维护：
    • 当前结尾的最大子串权值；
    • 全局最大权值；
  4. 返回最终结果。

五、复杂度分析

  • 时间复杂度： \[ O(n) \] 其中 \(n = |s|\)

  • 空间复杂度： \[ O(1) \] 仅使用常数大小的辅助数组与变量

六、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
class Solution {
public:
    static const int maxn = 1e5 + 5;

    int maximumCostSubstring(string s, string chars, vector<int>& vals) {
        int w[26];

        // 1. 初始化默认权值：'a' -> 1, ..., 'z' -> 26
        for (int i = 0; i < 26; ++i)
            w[i] = i + 1;

        // 2. 覆盖 chars 中出现的字符权值
        for (int i = 0; i < chars.size(); ++i)
            w[chars[i] - 'a'] = vals[i];

        // 3. Kadane 算法初始化
        int pre_v = w[s[0] - 'a'];
        int mx = max(0, pre_v);   // 允许空子串

        // 4. 动态规划迭代
        for (int i = 1; i < s.size(); ++i) {
            int v = w[s[i] - 'a'];
            pre_v = max(v, v + pre_v);
            mx = max(mx, pre_v);
        }

        return mx;
    }
};