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 (1-indexed) in the alphabet.
    <ul>
	<li>For example, the value of <code>&#39;a&#39;</code> is <code>1</code>, the value of <code>&#39;b&#39;</code> is <code>2</code>, and so on. The value of <code>&#39;z&#39;</code> is <code>26</code>.</li>
</ul>
</li>
<li>Otherwise, assuming <code>i</code> is the index where the character occurs in the string <code>chars</code>, then its value is <code>vals[i]</code>.</li>

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

Solutions

Solution 1: Prefix sum + Maintain the minimum prefix sum

According to the description of the problem, we traverse each character cc in the string ss, obtain its corresponding value vv, and then update the current prefix sum tot=tot+vtot=tot+v. Then, the cost of the maximum cost substring ending with cc is tottot minus the minimum prefix sum mimi, that is, tot−mitot-mi. We update the answer ans=max(ans,tot−mi)ans=max(ans,tot-mi) and maintain the minimum prefix sum mi=min(mi,tot)mi=min(mi,tot).

After the traversal is over, return the answer ansans.

The time complexity is O(n)O(n), and the space complexity is O(C)O(C). Where nn is the length of the string ss; and CC is the size of the character set, which is 2626 in this problem.

Python Code
 1
 2
 3
 4
 5
 6
 7
 8
 9
10

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

Java Code
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21

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;
    }
}

C++ Code
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

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;
    }
};

Go Code
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

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, tot-mi)
		mi = min(mi, tot)
	}
	return
}

TypeScript Code
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

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;
}

Solution 2: Convert to the maximum subarray sum problem

We can consider the value vv of each character cc as an integer, so the actual problem is to solve the maximum subarray sum problem.

We use the variable ff to maintain the cost of the maximum cost substring ending with the current character cc. Each time we traverse to a character cc, we update f=max(f,0)+vf=max(f, 0) + v. Then we update the answer ans=max(ans,f)ans=max(ans,f).

The time complexity is O(n)O(n), and the space complexity is O(C)O(C). Where nn is the length of the string ss; and CC is the size of the character set, which is 2626 in this problem.

Python Code
1
2
3
4
5
6
7
8
9

class Solution:
    def maximumCostSubstring(self, s: str, chars: str, vals: List[int]) -> int:
        d = {c: v for c, v in zip(chars, vals)}
        ans = f = 0
        for c in s:
            v = d.get(c, ord(c) - ord('a') + 1)
            f = max(f, 0) + v
            ans = max(ans, f)
        return ans

Java Code
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20

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, f = 0;
        int n = s.length();
        for (int i = 0; i < n; ++i) {
            int v = d[s.charAt(i) - 'a'];
            f = Math.max(f, 0) + v;
            ans = Math.max(ans, f);
        }
        return ans;
    }
}

C++ Code
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

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, f = 0;
        for (char& c : s) {
            int v = d[c - 'a'];
            f = max(f, 0) + v;
            ans = max(ans, f);
        }
        return ans;
    }
};

Go Code
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

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]
	}
	f := 0
	for _, c := range s {
		v := d[c-'a']
		f = max(f, 0) + v
		ans = max(ans, f)
	}
	return
}

TypeScript Code
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

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 f = 0;
    for (const c of s) {
        f = Math.max(f, 0) + d[c.charCodeAt(0) - 97];
        ans = Math.max(ans, f);
    }
    return ans;
}