Find the Substring With Maximum Cost — LeetCode 2606 Python Solution

The problem

You are given a string s, a string chars of distinct characters and an integer array vals of the same length as chars. The cost of the substring is the sum of the values of each character in the substring.

Example

Input

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

Output

2

Explanation

The value of the characters "a" and "d" is 1 and -1000 respectively.

Python solution

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

Complexity

Pattern: Dynamic Programming

Define a state, write the transition, and stop recomputing the same subproblem. LeetCode 2606. Find the Substring With Maximum Cost is filed here because LeetCode tags it Dynamic Programming, which is the vocabulary this hub collects.

The dynamic programming guide has the Python template for the pattern and the 481 LeetCode problems that use it.

Related problems