Find the Substring With Maximum Cost
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 a substring is the sum of the values of each character in the substring. The cost of an empty string is considered 0.
The value of a character is defined in the following way:
- If the character is not in the string
chars, then its value is its corresponding position (1-indexed) in the alphabet. - For example, the value of
'a'is1, the value of'b'is2, and so on. The value of'z'is26. - Otherwise, assuming
iis the index where the character occurs in the stringchars, then its value isvals[i].
Return the maximum cost among all substrings of the string s.
Example 1
Input
s = "adaa", chars = "d", vals = [-1000]Output
2The substring with the maximum cost is "aa", whose cost is 1 + 1 = 2.
Example 2
Input
s = "abc", chars = "abc", vals = [-1,-1,-1]Output
0All non-empty substrings have negative cost, so the empty substring has the maximum cost of 0.
Constraints
- 1 <= s.length <= 10^5
- 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