Medium

题目描述

给你一个字符串 s，一个由不同字符组成的字符串 chars 和一个与 chars 长度相同的整数数组 vals。

子字符串的代价是子字符串中每个字符的值的总和。空字符串的代价被认为是 0。

字符的值定义如下：

  • 如果字符不在字符串 chars 中，那么它的值是它在字母表中对应的位置（从 1 开始计数）。
    • 例如，‘a’ 的值是 1，‘b’ 的值是 2，以此类推。‘z’ 的值是 26。
  • 否则，假设 i 是字符在字符串 chars 中出现的索引，那么它的值是 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 <= 10^5
  • s 由小写英文字母组成
  • 1 <= chars.length <= 26
  • chars 由不同的小写英文字母组成
  • vals.length == chars.length
  • -1000 <= vals[i] <= 1000

解题思路

这道题是一个经典的最大子数组和问题的变形，可以使用Kadane算法来解决。

解题思路：

  1. 字符值映射：首先需要为字符串中的每个字符建立一个值的映射。对于在 chars 中的字符，使用 vals 数组中对应的值；对于不在 chars 中的字符，使用其在字母表中的位置（a=1, b=2, …）。

  2. 转换为数组：将字符串 s 转换为一个整数数组，其中每个元素代表对应字符的值。

  3. 应用Kadane算法：在转换后的数组上应用Kadane算法找到最大子数组和。需要注意的是，由于空子字符串的代价为0，我们需要确保结果不小于0。

Kadane算法核心思想：

  • 维护两个变量：currentSum（当前子数组和）和 maxSum（目前为止的最大子数组和）
  • 遍历数组时，对于每个元素，我们选择要么将其加入当前子数组，要么从该元素重新开始一个新的子数组
  • 即：currentSum = max(currentSum + arr[i], arr[i])

由于题目允许空子字符串（代价为0），最终答案需要与0取最大值。

代码实现

class Solution {
public:
    int maximumCostSubstring(string s, string chars, vector<int>& vals) {
        unordered_map<char, int> charValue;
        
        // 建立字符到值的映射
        for (int i = 0; i < chars.length(); i++) {
            charValue[chars[i]] = vals[i];
        }
        
        int maxCost = 0; // 空子字符串的代价
        int currentCost = 0;
        
        // 使用Kadane算法
        for (char c : s) {
            int value;
            if (charValue.find(c) != charValue.end()) {
                value = charValue[c];
            } else {
                value = c - 'a' + 1; // 字母表位置
            }
            
            currentCost = max(currentCost + value, value);
            maxCost = max(maxCost, currentCost);
        }
        
        return maxCost;
    }
};

class Solution:
    def maximumCostSubstring(self, s: str, chars: str, vals: List[int]) -> int:
        # 建立字符到值的映射
        char_value = {}
        for i in range(len(chars)):
            char_value[chars[i]] = vals[i]
        
        max_cost = 0  # 空子字符串的代价
        current_cost = 0
        
        # 使用Kadane算法
        for c in s:
            if c in char_value:
                value = char_value[c]
            else:
                value = ord(c) - ord('a') + 1  # 字母表位置
            
            current_cost = max(current_cost + value, value)
            max_cost = max(max_cost, current_cost)
        
        return max_cost

public class Solution {
    public int MaximumCostSubstring(string s, string chars, int[] vals) {
        Dictionary<char, int> charValue = new Dictionary<char, int>();
        
        // 建立字符到值的映射
        for (int i = 0; i < chars.Length; i++) {
            charValue[chars[i]] = vals[i];
        }
        
        int maxCost = 0; // 空子字符串的代价
        int currentCost = 0;
        
        // 使用Kadane算法
        foreach (char c in s) {
            int value;
            if (charValue.ContainsKey(c)) {
                value = charValue[c];
            } else {
                value = c - 'a' + 1; // 字母表位置
            }
            
            currentCost = Math.Max(currentCost + value, value);
            maxCost = Math.Max(maxCost, currentCost);
        }
        
        return maxCost;
    }
}

var maximumCostSubstring = function(s, chars, vals) {
    const charValue = new Map();
    
    // 建立字符到值的映射
    for (let i = 0; i < chars.length; i++) {
        charValue.set(chars[i], vals[i]);
    }
    
    let maxCost = 0; // 空子字符串的代价
    let currentCost = 0;
    
    // 使用Kadane算法
    for (let c of s) {
        let value;
        if (charValue.has(c)) {
            value = charValue.get(c);
        } else {
            value = c.charCodeAt(0) - 'a'.charCodeAt(0) + 1; // 字母表位置
        }
        
        currentCost = Math.max(currentCost + value, value);
        maxCost = Math.max(maxCost, currentCost);
    }
    
    return maxCost;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型大小说明
时间复杂度O(n + m)n是字符串s的长度，m是chars的长度。需要O(m)建立映射，O(n)遍历字符串
空间复杂度O(m)需要存储字符到值的映射，最多m个键值对

相关题目