You are given a string s, a string chars of distinct characters, and an integer array vals of the same length as chars.

The value of each character is defined as follows:

• If the character appears in chars at index i, its value is vals[i].

• Otherwise, its value is its $1$ based position in the alphabet (that is, 'a' has a value of $1$, 'b' has a value of $2$, and so on up to 'z' with a value of $26$).

The cost of a substring is the sum of the values of its characters. The cost of an empty substring is defined as $0$.

Return the maximum cost among all substrings of s.

Constraints:

• $1 \leq$ s.length $\leq 10^5$

• s consists of lowercase English letters.

• $1 \leq$ chars.length $\leq 26$

• chars consists of distinct lowercase English letters.

• vals.length $==$ chars.length

• $-1000 \leq$ vals[i] $\leq 1000$

Input: s = "k"-str, chars = "k"-str, vals = [999]-List[int]
Output: 999-int
Explanation: The character k has the assigned value 999, so the maximum-cost substring is "k" with cost 999.

Input: s = "wxy"-str, chars = "wxy"-str, vals = [-4, -2, -9]-List[int]
Output: 0-int
Explanation: All characters have negative values, so the empty substring has the maximum cost of 0.

Input: s = "abczd"-str, chars = "c"-str, vals = [-100]-List[int]
Output: 30-int
Explanation: The character values are a = 1, b = 2, c = -100, z = 26, and d = 4. The substring "zd" has the maximum cost, 30.

Input: s = "pqrspq"-str, chars = "pqs"-str, vals = [-10, 20, -5]-List[int]
Output: 43-int
Explanation: The character values are p = -10, q = 20, r = 18, and s = -5. The substring "qrspq" has cost 20 + 18 - 5 - 10 + 20 = 43.

Now, let’s take a moment to make sure you’ve correctly understood the problem. The quiz below helps you check if you’re solving the correct problem:

We have a game for you to play. Rearrange the logical building blocks to develop a clearer understanding of how to solve this problem.

Implement your solution in the following coding playground.