题目描述
给你一个字符串 s
,一个字符 互不相同 的字符串 chars
和一个长度与 chars
相同的整数数组 vals
。
子字符串的开销 是一个子字符串中所有字符对应价值之和。空字符串的开销是 0
。
字符的价值 定义如下:
- 如果字符不在字符串
chars
中,那么它的价值是它在字母表中的位置(下标从 1 开始)。- 比方说,
'a'
的价值为1
,'b'
的价值为2
,以此类推,'z'
的价值为26
。
- 比方说,
- 否则,如果这个字符在
chars
中的位置为i
,那么它的价值就是vals[i]
。
请你返回字符串 s
的所有子字符串中的最大开销。
样例
输入:s = "adaa", chars = "d", vals = [-1000]
输出:2
解释:字符 "a" 和 "d" 的价值分别为 1 和 -1000。
最大开销子字符串是 "aa",它的开销为 1 + 1 = 2。
2 是最大开销。
输入:s = "abc", chars = "abc", vals = [-1,-1,-1]
输出:0
解释:字符 "a","b" 和 "c" 的价值分别为 -1,-1 和 -1。
最大开销子字符串是 "",它的开销为 0 。
0 是最大开销。
限制
1 <= s.length <= 10^5
s
只包含小写英文字母。1 <= chars.length <= 26
chars
只包含小写英文字母,且 互不相同。vals.length == chars.length
-1000 <= vals[i] <= 1000
算法
(动态规划) $O(n + \Sigma)$
- 预处理每个字符的价值。
- 设状态 $f(i)$ 表示遍历了前 $i$ 个字符的最大价值。
- 初始时,$f(0) = 0$,其余待定。
- 转移时,对于第 $i$ 个字符,可以选择与前面的 $i-1$ 组成子串,或者单独作为一个新的子串的开始,转移 $f(i) = \max(v(i), f(i - 1) + v(i))$。
- 最终答案为 $\max(0, \max(f(i)))$。
- 可以通过一个变量 $f$ 来替代状态的存储。
时间复杂度
- 预处理字符价值的时间复杂度为 $O(\Sigma)$。
- 动态规划的状态数为 $O(n)$,转移时间为常数,故时间复杂度为 $O(n)$。
- 总时间复杂度为 $O(n + \Sigma)$。
空间复杂度
- 需要 $O(\Sigma)$ 的额外空间存储每个字符的代价。
C++ 代码
class Solution {
public:
int maximumCostSubstring(string s, string chars, vector<int>& vals) {
vector<int> v(26);
for (int i = 0; i < 26; i++)
v[i] = i + 1;
for (int i = 0; i < chars.size(); i++)
v[chars[i] - 'a'] = vals[i];
int f = 0, ans = 0;
for (char c : s) {
if (f < 0) f = v[c - 'a'];
else f += v[c - 'a'];
ans = max(ans, f);
}
return ans;
}
};