LeetCode 2606. 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 the 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 the 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' is 1, the value of 'b' is 2, and so on. The value of 'z' is 26.

• Otherwise, assuming i is the index where the character occurs in the string chars, then its value is vals[i].

Return the maximum cost among all substrings of the string s.

Example 1:

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

Output: 2

Explanation: 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

Explanation: 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.

 建一个hashmap，把chars的字符对应的值放到map中，

然后遍历字符串，如果在map中，将对应的值放到数组中，如果没在，就-‘a’+1 返回数组，

最后遍历数组判断最大值，但是如果sum小于0了，就没必要继续保留了，直接sum=0，继续遍历剩下的数组。

返回最大值即可；

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

Runtime: 24 ms, faster than 100.00% of Java online submissions for Find the Substring With Maximum Cost.

Memory Usage: 43.5 MB, less than 100.00% of Java online submissions for Find the Substring With Maximum Cost.