Welcome to Subscribe On Youtube
2606. Find the Substring With Maximum Cost
Description
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 (1indexed) in the alphabet. For example, the value of
'a'
is1
, the value of'b'
is2
, and so on. The value of'z'
is26
.
 For example, the value of
 Otherwise, assuming
i
is 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: 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 <= 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
Solutions
Solution 1: Prefix sum + Maintain the minimum prefix sum
According to the description of the problem, we traverse each character $c$ in the string $s$, obtain its corresponding value $v$, and then update the current prefix sum $tot=tot+v$. Then, the cost of the maximum cost substring ending with $c$ is $tot$ minus the minimum prefix sum $mi$, that is, $totmi$. We update the answer $ans=max(ans,totmi)$ and maintain the minimum prefix sum $mi=min(mi,tot)$.
After the traversal is over, return the answer $ans$.
The time complexity is $O(n)$, and the space complexity is $O(C)$. Where $n$ is the length of the string $s$; and $C$ is the size of the character set, which is $26$ in this problem.
Solution 2: Convert to the maximum subarray sum problem
We can consider the value $v$ of each character $c$ as an integer, so the actual problem is to solve the maximum subarray sum problem.
We use the variable $f$ to maintain the cost of the maximum cost substring ending with the current character $c$. Each time we traverse to a character $c$, we update $f=max(f, 0) + v$. Then we update the answer $ans=max(ans,f)$.
The time complexity is $O(n)$, and the space complexity is $O(C)$. Where $n$ is the length of the string $s$; and $C$ is the size of the character set, which is $26$ in this problem.

class Solution { public int maximumCostSubstring(String s, String chars, int[] vals) { int[] d = new int[26]; for (int i = 0; i < d.length; ++i) { d[i] = i + 1; } int m = chars.length(); for (int i = 0; i < m; ++i) { d[chars.charAt(i)  'a'] = vals[i]; } int ans = 0, tot = 0, mi = 0; int n = s.length(); for (int i = 0; i < n; ++i) { int v = d[s.charAt(i)  'a']; tot += v; ans = Math.max(ans, tot  mi); mi = Math.min(mi, tot); } return ans; } }

class Solution { public: int maximumCostSubstring(string s, string chars, vector<int>& vals) { vector<int> d(26); iota(d.begin(), d.end(), 1); int m = chars.size(); for (int i = 0; i < m; ++i) { d[chars[i]  'a'] = vals[i]; } int ans = 0, tot = 0, mi = 0; for (char& c : s) { int v = d[c  'a']; tot += v; ans = max(ans, tot  mi); mi = min(mi, tot); } return ans; } };

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

func maximumCostSubstring(s string, chars string, vals []int) (ans int) { d := [26]int{} for i := range d { d[i] = i + 1 } for i, c := range chars { d[c'a'] = vals[i] } tot, mi := 0, 0 for _, c := range s { v := d[c'a'] tot += v ans = max(ans, totmi) mi = min(mi, tot) } return }

function maximumCostSubstring(s: string, chars: string, vals: number[]): number { const d: number[] = Array.from({ length: 26 }, (_, i) => i + 1); for (let i = 0; i < chars.length; ++i) { d[chars.charCodeAt(i)  97] = vals[i]; } let ans = 0; let tot = 0; let mi = 0; for (const c of s) { tot += d[c.charCodeAt(0)  97]; ans = Math.max(ans, tot  mi); mi = Math.min(mi, tot); } return ans; }