找到最大开销的子字符串-LeetCode

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

🎯 问题描述（来源于LeetCode）

描述：
给你一个字符串 s，一个字符数组 chars 和一个整数数组 vals，其中 chars[i] 对应的权值为 vals[i]。
对于未出现在 chars 中的字符，其权值为它在字母表中的位置（'a' 为 1，'b' 为 2，…，'z' 为 26）。
定义子串的开销为子串中所有字符的权值之和。要求返回 s 的所有子串中的最大开销。
注意，空子串的开销为 0。

说明：

• 子串是连续的。
• 若所有子串的开销均为负数，则答案为 0（即选择空子串）。

示例：

• 示例 1：

输入: s = "adaa", chars = "d", vals = [-1000]
输出: 2
解释: 字符 'd' 的权值为 -1000，'a' 的权值为 1。最佳子串为 "aa"，开销 = 1+1=2。

• 示例 2：

输入: s = "abc", chars = "abc", vals = [-1,-1,-1]
输出: 0
解释: 所有字符权值均为 -1，任何非空子串开销为负，因此选择空子串得 0。

💻 解题思路

思路：Kadane 算法（最大子数组和）

算法步骤

1. 构建字典 cost，将 chars 中的字符映射到对应的 vals。
2. 初始化 max_sum = 0（允许空子串），cur_sum = 0。
3. 遍历字符串 s 的每个字符 ch：
   • 获取权值：若 ch 在 cost 中则 val = cost[ch]，否则 val = ord(ch) - ord('a') + 1。
   • 使用 Kadane 公式更新 cur_sum = max(val, cur_sum + val)。
   • 更新全局最大值 max_sum = max(max_sum, cur_sum)。
4. 返回 max_sum。

代码实现

from typing import List

class Solution:
    def maximumCostSubstring(self, s: str, chars: str, vals: List[int]) -> int:
        # 构建权值映射
        cost = {}
        for c, v in zip(chars, vals):
            cost[c] = v
        
        max_sum = 0          # 初始为0，允许空子串
        cur_sum = 0
        for ch in s:
            # 获取当前字符的权值
            if ch in cost:
                val = cost[ch]
            else:
                val = ord(ch) - ord('a') + 1
            # Kadane 状态转移
            cur_sum = max(val, cur_sum + val)
            max_sum = max(max_sum, cur_sum)
        return max_sum

📊 性能分析

• 时间复杂度：$O(n)$，其中 $n$ 为 s 的长度。
• 空间复杂度：$O(1)$（映射表大小最多 26）。

思考

该解法将问题转化为求最大子数组和，通过 Kadane 算法在线性时间内解决。代码简洁，利用字典映射自定义权值，并正确处理了未定义字符的默认权值。初始化 max_sum = 0 允许选择空子串，符合题目要求。这是本题的标准解法。