Find the Substring With Maximum Cost — Problem & Solution
Find the Substring With Maximum Cost solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem.
Find the Substring With Maximum Cost is a medium coding problem on arrays, strings and hash table, asked in Amazon and Google interviews.
- Difficulty: Medium
- Topics: Arrays, Strings, Hash Table, Dynamic Programming
- Asked at: Amazon, Google
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
You are given a lowercase string s, a string chars of distinct lowercase letters, and an integer array vals of the same length as chars.
The value of a letter is:
vals[i]if the letter ischars[i];- otherwise its 1-indexed position in the alphabet (
'a'is 1,'b'is 2, …,'z'is 26).
The cost of a substring is the sum of the values of its letters, and the cost of the empty string is 0.
Return the maximum cost over all substrings of s (the empty substring included).
Example 1
Input: s = "kairo", chars = "i", vals = [-20]
Output: 33
Explanation: Values are k = 11, a = 1, i = -20, r = 18, o = 15. The best substring is `"ro"`.
Example 2
Input: s = "abc", chars = "abc", vals = [-1,-1,-1]
Output: 0
Explanation: Every letter is negative, so the empty substring is best.
Example 3
Input: s = "xyz", chars = "y", vals = [-100]
Output: 26
Constraints
1 <= s.length <= 10^5s consists of lowercase English letters1 <= chars.length <= 26chars consists of distinct lowercase English lettersvals.length == chars.length-1000 <= vals[i] <= 1000
Hints for Find the Substring With Maximum Cost
Hint 1
First turn
sinto an array of numbers: the value of each letter.Hint 2
Now you want the maximum sum of a contiguous subarray, where the empty subarray (sum 0) is allowed.
Hint 3
Kadane's algorithm: keep the best sum of a subarray ending here,
cur = max(0, cur + value), and track the maximum.
How to solve Find the Substring With Maximum Cost
Map every letter to its value; the question becomes the maximum subarray sum with the empty subarray allowed, which Kadane's algorithm solves in one pass.
Approach
- Build
cost[26]withcost[c] = c + 1, then overwritecost[chars[i]] = vals[i]for eachi. - Scan
skeepingcur, the best cost of a substring ending at the current position (or empty):cur = max(0, cur + cost[s[i]]). - Track
best = max(best, cur); it starts at 0 for the empty substring.
Why it works
The best substring ending at position i either extends the best one ending at i - 1 or starts fresh; starting fresh (an empty prefix) is better exactly when the running sum went negative. Taking the maximum of these over all i, together with the empty substring, gives the overall maximum.
Complexity
- Time —
O(n + 26) - Space —
O(26)
Pitfalls
- The empty substring is allowed, so the answer is never negative.
- Letters not in
charskeep their alphabet position as value. chars[i]pairs withvals[i]by index — build the lookup table once instead of searchingcharsfor every letter.
Reference solution
Python
from typing import List
def maximumCostSubstring(s: str, chars: str, vals: List[int]) -> int:
cost = [i + 1 for i in range(26)]
for ch, v in zip(chars, vals):
cost[ord(ch) - 97] = v
best = cur = 0
for ch in s:
cur = max(0, cur + cost[ord(ch) - 97])
best = max(best, cur)
return bestJava
public static int maximumCostSubstring(String s, String chars, int[] vals) {
int[] cost = new int[26];
for (int i = 0; i < 26; i++) cost[i] = i + 1;
for (int j = 0; j < chars.length(); j++) cost[chars.charAt(j) - 'a'] = vals[j];
int best = 0, cur = 0;
for (int k = 0; k < s.length(); k++) {
cur = Math.max(0, cur + cost[s.charAt(k) - 'a']);
best = Math.max(best, cur);
}
return best;
}C++
int maximumCostSubstring(string s, string chars, vector<int>& vals) {
int cost[26];
for (int i = 0; i < 26; i++) cost[i] = i + 1;
for (size_t j = 0; j < chars.size(); j++) cost[chars[j] - 'a'] = vals[j];
int best = 0, cur = 0;
for (char ch : s) {
cur = max(0, cur + cost[ch - 'a']);
best = max(best, cur);
}
return best;
}JavaScript
var maximumCostSubstring = function(s, chars, vals) {
var cost = [];
for (var i = 0; i < 26; i++) cost.push(i + 1);
for (var j = 0; j < chars.length; j++) cost[chars.charCodeAt(j) - 97] = vals[j];
var best = 0, cur = 0;
for (var k = 0; k < s.length; k++) {
cur = Math.max(0, cur + cost[s.charCodeAt(k) - 97]);
if (cur > best) best = cur;
}
return best;
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.