What is the primary technique to solve the Find the Substring With Maximum Cost problem?

The primary technique involves using array scanning along with hash lookup for character values, ensuring efficient substring cost calculation.

How do I handle negative character values in this problem?

You should carefully track the total cost as you iterate through the string and reset or skip negative cost substrings, potentially choosing the empty substring.

Can this problem be solved in linear time?

Yes, by using an array scanning technique with hash lookups, you can solve this problem in O(n) time complexity.

What is the space complexity of this problem?

The space complexity is O(m), where m is the number of distinct characters in chars, which is at most 26.

Is dynamic programming necessary for solving this problem?

Dynamic programming is useful for optimizing substring cost calculations, though simple array scanning with partial sums may also suffice.

#2606

Medium

auto_awesome数组·哈希·扫描

LeetCode 题解工作台

找到最大开销的子字符串

给你一个字符串 s ，一个字符互不相同的字符串 chars 和一个长度与 chars 相同的整数数组 vals 。子字符串的开销是一个子字符串中所有字符对应价值之和。空字符串的开销是 0 。字符的价值定义如下：如果字符不在字符串 chars 中，那么它的价值是它在字母表中的位置（下标从…

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

题目描述

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

lightbulb

解题思路

方法一：前缀和 + 维护前缀和的最小值

我们根据题目描述，遍历字符串 $s$ 的每个字符 $c$ ，求出其对应的价值 $v$ ，然后更新当前的前缀和 $tot=tot+v$ ，那么以 $c$ 结尾的最大开销子字符串的开销为 $tot$ 减去前缀和的最小值 $mi$ ，即 $tot-mi$ ，我们更新答案 $ans=max(ans,tot-mi)$ ，并维护前缀和的最小值 $mi=min(mi,tot)$ 。

遍历结束后返回答案 $ans$ 即可。

时间复杂度 $O(n)$ ，空间复杂度 $O(C)$ 。其中 $n$ 为字符串 $s$ 的长度；而 $C$ 为字符集的大小，本题中 $C=26$ 。

1

2

3

4

5

6

7

8

9

10

11

class Solution:
    def maximumCostSubstring(self, s: str, chars: str, vals: List[int]) -> int:
        d = {c: v for c, v in zip(chars, vals)}
        ans = tot = mi = 0
        for c in s:
            v = d.get(c, ord(c) - ord('a') + 1)
            tot += v
            ans = max(ans, tot - mi)
            mi = min(mi, tot)
        return ans

speed

复杂度分析

指标	值
时间	Depends on the final approach
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

question_mark
Look for the ability to efficiently use hash lookups during the array scan.
question_mark
Evaluate if the candidate can handle negative values in substring calculations.
question_mark
Assess if the candidate can optimize space complexity with the use of a mapping or array.

warning

常见陷阱

外企场景

error
Misunderstanding how to map character values to substrings efficiently.
error
Failing to handle negative character values correctly, potentially missing the optimal empty substring.
error
Overcomplicating the approach by trying to check every possible substring without utilizing dynamic programming or array scanning.

swap_horiz

进阶变体

外企场景

arrow_right_alt
What if the input string s contains only one character?
arrow_right_alt
How would the solution change if the characters in chars are not distinct?
arrow_right_alt
What if there are multiple substrings with the same maximum cost?

help

常见问题

外企场景

继续练习

#2707 字符串中的额外字符 #3316 从原字符串里进行删除操作的最多次数 #2597 美丽子集的数目