找到最大开销的子字符串

标签: 数组 哈希表 字符串 动态规划

难度: Medium

给你一个字符串 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 <= 105
  • s 只包含小写英文字母。
  • 1 <= chars.length <= 26
  • chars 只包含小写英文字母，且 互不相同 。
  • vals.length == chars.length
  • -1000 <= vals[i] <= 1000

Submission

运行时间: 81 ms

内存: 16.5 MB

class Solution:
    def maximumCostSubstring(self, s: str, chars: str, vals: List[int]) -> int:
        res, cur, d = 0, 0, {c: v for c, v in zip(ascii_lowercase, range(1, 27))}
        d.update(zip(chars, vals))
        for x in map(d.__getitem__, s):
            if (cur := cur + x) < 0: cur = 0
            if res < cur: res = cur
        return res

Explain

The solution implements the Kadane's algorithm to find the maximum sum of a contiguous subarray, where the array elements are the costs of characters in the string 's'. Initially, a dictionary 'd' is created to map each lowercase letter to its alphabetical index. This mapping is then updated with the given 'chars' and their corresponding 'vals'. During the iteration over the string 's', the value of each character is retrieved from the dictionary 'd', and the current sum 'cur' is updated. If 'cur' drops below zero, it is reset to zero. The maximum observed 'cur' is tracked with 'res'. This ensures that we are always considering the maximum cost of any contiguous substring.

时间复杂度: O(n)

空间复杂度: O(1)

# Definition of the solution class

class Solution:
    def maximumCostSubstring(self, s: str, chars: str, vals: List[int]) -> int:
        # Initialize the maximum result, current sum, and dictionary for character costs
        res, cur = 0, 0
        d = {c: v for c, v in zip(ascii_lowercase, range(1, 27))}  # Mapping from 'a' to 'z' to their 1-based index
        d.update(zip(chars, vals))  # Update with custom values for specific characters
        # Iterate over each character in string 's'
        for x in map(d.__getitem__, s):
            cur += x  # Update the current subarray sum
            if cur < 0: cur = 0  # Reset current sum if it goes negative
            res = max(res, cur)  # Update the maximum result found
        return res  # Return the maximum subarray sum found

Explore

Kadane's algorithm 是一种有效的算法，用于找出数组中具有最大和的连续子数组。在这个问题中，我们需要找到字符串中某个连续子字符串的最大开销，这与找到最大和的连续子数组的问题本质相同。通过将每个字符转换为其相应的数值开销，我们可以将问题转化为一个典型的最大子数组和问题，从而利用 Kadane's algorithm 来解决。该算法的时间复杂度为O(n)，因此在处理大数据量时仍然非常高效。

在 Kadane's algorithm 中，如果当前累积开销 `cur` 变为负数，意味着将这部分累积加入到后续的子数组中只会降低其总和。因此，最优的策略是从下一个元素开始重新计算新的子数组和，即将 `cur` 重置为0。这样做是为了确保我们总是从可能增加总和的位置开始计算，从而找到可能的最大子数组和。

在 Python 中，字典的键是唯一的。当使用 `d.update(zip(chars, vals))` 更新字典时，如果 `chars` 中的字符已经存在于字典 `d` 中，其对应的值将被 `vals` 中相应位置的值覆盖。这确保了每个字符最终都会映射到一个具体的值。因此，即使存在重复的字符更新，也只会影响该字符的最终值，而不会引入重复的键值对。这种处理方式符合题目要求，即可能需要根据 `chars` 和 `vals` 更改特定字符的值。

在题解中没有特别处理`chars`和`vals`长度不匹配的情况。`zip(chars, vals)`函数将创建一个元组列表，其长度由最短的输入序列决定。如果`chars`比`vals`长，那么超出`vals`长度的部分字符将不会被包含在更新字典的操作中；如果`vals`比`chars`长，那么超出`chars`长度的部分值将被忽略。在实际应用中，应该确保`chars`和`vals`的长度相匹配，或者在代码中添加逻辑来处理长度不匹配的情况，以避免潜在的错误或逻辑问题。