找到最大开销的子字符串

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.

 

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

/*
 * 思路：
 * 1. 创建一个哈希映射，用于存储 chars 中字符对应的 vals 值。
 * 2. 使用流操作遍历字符串 s，对于每个字符，获取其对应的价值（在哈希映射中或通过其字母表位置计算）。
 * 3. 使用流操作找到最大子数组和，该和即为最大开销。
 */

import java.util.HashMap;
import java.util.Map;
import java.util.stream.IntStream;

public class Solution {
    public int maximumCostSubstring(String s, String chars, int[] vals) {
        Map<Character, Integer> charValueMap = new HashMap<>();
        for (int i = 0; i < chars.length(); i++) {
            charValueMap.put(chars.charAt(i), vals[i]);
        }
        int[] maxCost = {0};
        int[] currentCost = {0};
        s.chars().forEach(c -> {
            int value = charValueMap.getOrDefault((char) c, c - 'a' + 1);
            currentCost[0] = Math.max(value, currentCost[0] + value);
            maxCost[0] = Math.max(maxCost[0], currentCost[0]);
        });
        return maxCost[0];
    }
}

The solution implements the Kadane's algorithm to find the maximum sum of a contiguous subarray, where the array elements are the costs of characters in the string 's'. Initially, a dictionary 'd' is created to map each lowercase letter to its alphabetical index. This mapping is then updated with the given 'chars' and their corresponding 'vals'. During the iteration over the string 's', the value of each character is retrieved from the dictionary 'd', and the current sum 'cur' is updated. If 'cur' drops below zero, it is reset to zero. The maximum observed 'cur' is tracked with 'res'. This ensures that we are always considering the maximum cost of any contiguous substring.

O(n)

O(1)