class Solution {
public:
int maximumCostSubstring(string s, string chars, vector<int>& vals) {
}
};
6328. 找到最大开销的子字符串
给你一个字符串 s ，一个字符 互不相同 的字符串 chars 和一个长度与 chars 相同的整数数组 vals 。
子字符串的开销 是一个子字符串中所有字符对应价值之和。空字符串的开销是 0 。
字符的价值 定义如下：
chars 中，那么它的价值是它在字母表中的位置（下标从 1 开始）。
'a' 的价值为 1 ，'b' 的价值为 2 ，以此类推，'z' 的价值为 26 。chars 中的位置为 i ，那么它的价值就是 vals[i] 。请你返回字符串 s 的所有子字符串中的最大开销。
示例 1：
输入：s = "adaa", chars = "d", vals = [-1000] 输出：2 解释：字符 "a" 和 "d" 的价值分别为 1 和 -1000 。 最大开销子字符串是 "aa" ，它的开销为 1 + 1 = 2 。 2 是最大开销。
示例 2：
输入：s = "abc", chars = "abc", vals = [-1,-1,-1] 输出：0 解释：字符 "a" ，"b" 和 "c" 的价值分别为 -1 ，-1 和 -1 。 最大开销子字符串是 "" ，它的开销为 0 。 0 是最大开销。
提示：
1 <= s.length <= 105s 只包含小写英文字母。1 <= chars.length <= 26chars 只包含小写英文字母，且 互不相同 。vals.length == chars.length-1000 <= vals[i] <= 1000原站题解
golang 解法, 执行用时: 12 ms, 内存消耗: 6.1 MB, 提交时间: 2023-04-02 12:28:32
func maximumCostSubstring(s, chars string, vals []int) (ans int) {
mapping := [26]int{}
for i := range mapping {
mapping[i] = i + 1
}
for i, c := range chars {
mapping[c-'a'] = vals[i]
}
f := 0
for _, c := range s {
f = max(f, 0) + mapping[c-'a']
ans = max(ans, f)
}
return ans
}
func max(a, b int) int { if a < b { return b }; return a }
java 解法, 执行用时: 3 ms, 内存消耗: 42.2 MB, 提交时间: 2023-04-02 12:28:20
class Solution {
public int maximumCostSubstring(String s, String chars, int[] vals) {
var mapping = new int[26];
for (int i = 0; i < 26; ++i)
mapping[i] = i + 1;
for (int i = 0; i < vals.length; ++i)
mapping[chars.charAt(i) - 'a'] = vals[i];
// 最大子段和（允许子数组为空）
int ans = 0, f = 0;
for (char c : s.toCharArray()) {
f = Math.max(f, 0) + mapping[c - 'a'];
ans = Math.max(ans, f);
}
return ans;
}
}
python3 解法, 执行用时: 260 ms, 内存消耗: 15.7 MB, 提交时间: 2023-04-02 12:28:08
class Solution:
def maximumCostSubstring(self, s: str, chars: str, vals: List[int]) -> int:
mapping = dict(zip(chars, vals))
ans = f = 0
for c in s:
f = max(f, 0) + mapping.get(c, ord(c) - ord('a') + 1)
ans = max(ans, f)
return ans