#2606

Medium

auto_awesomeArray scanning plus hash lookup

LeetCode Problem Workspace

Find the Substring With Maximum Cost

Find the Substring With Maximum Cost requires calculating substring values using a hash lookup for character costs, with dynamic scanning optimization.

array hash table string dynamic programming

Problem Statement

Given a string s, a string chars of distinct characters, and an integer array vals, you must calculate the maximum cost of any substring of s. The cost of each substring is determined by summing the values of its characters based on the vals array, where each character's value corresponds to its position in chars.

The task is to find the substring with the maximum total cost. The cost of an empty substring is 0. A solution should account for the fact that character values could be negative, meaning the highest cost substring could be one with only neutral or positive values, or potentially an empty string.

Examples

Example 1

Input: s = "adaa", chars = "d", vals = [-1000]

Output: 2

The value of the characters "a" and "d" is 1 and -1000 respectively. The substring with the maximum cost is "aa" and its cost is 1 + 1 = 2. It can be proven that 2 is the maximum cost.

Example 2

Input: s = "abc", chars = "abc", vals = [-1,-1,-1]

Output: 0

The value of the characters "a", "b" and "c" is -1, -1, and -1 respectively. The substring with the maximum cost is the empty substring "" and its cost is 0. It can be proven that 0 is the maximum cost.

Constraints

1 <= s.length <= 105
s consist of lowercase English letters.
1 <= chars.length <= 26
chars consist of distinct lowercase English letters.
vals.length == chars.length
-1000 <= vals[i] <= 1000

Solution Approach

Character Cost Mapping

Create a hash map or dictionary where each character in chars maps to its corresponding value in vals. This allows quick lookup of character values when iterating through the string s.

Array Scanning with Dynamic Programming

As you scan through string s, dynamically calculate the total cost of every possible substring. Update the maximum cost as you encounter higher totals. Efficiently use an array to store partial costs during the scan.

Handling Negative Values

Since values can be negative, carefully track when to reset or skip substrings with negative costs. An empty substring might be optimal if all character values are negative.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

The time complexity depends on the final approach. A straightforward scan through the string with hash lookups will result in O(n) time complexity, where n is the length of s. Space complexity will also depend on the number of unique characters, which is O(m) where m is the size of chars (at most 26).

What Interviewers Usually Probe

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

Common Pitfalls or Variants

Common pitfalls

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

Follow-up variants

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

FAQ

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.

terminal

Solution

Solution 1: Prefix sum + Maintain the minimum prefix sum

According to the description of the problem, we traverse each character $c$ in the string $s$, obtain its corresponding value $v$, and then update the current prefix sum $tot=tot+v$. Then, the cost of the maximum cost substring ending with $c$ is $tot$ minus the minimum prefix sum $mi$, that is, $tot-mi$. We update the answer $ans=max(ans,tot-mi)$ and maintain the minimum prefix sum $mi=min(mi,tot)$.

1

2

3

4

5

6

7

8

9

10

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

Solution 2: Convert to the maximum subarray sum problem

We can consider the value $v$ of each character $c$ as an integer, so the actual problem is to solve the maximum subarray sum problem.

1

2

3

4

5

6

7

8

9

10

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

Continue Practicing

#2707 extra characters in a string #3316 find maximum removals from source string #2597 the number of beautiful subsets