Find the Substring With Maximum Cost

Medium
1246.

Find the Substring With Maximum Cost

Find the Substring With Maximum Cost is a medium coding problem on arrays, strings and hash table, asked in Amazon and Google interviews.

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 is chars[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^5
  • s consists of lowercase English letters
  • 1 <= chars.length <= 26
  • chars consists of distinct lowercase English letters
  • vals.length == chars.length
  • -1000 <= vals[i] <= 1000
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {string} s
 * @param {string} chars
 * @param {number[]} vals
 * @return {number}
 */
var maximumCostSubstring = function(s, chars, vals) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

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.

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 is chars[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^5
  • s consists of lowercase English letters
  • 1 <= chars.length <= 26
  • chars consists of distinct lowercase English letters
  • vals.length == chars.length
  • -1000 <= vals[i] <= 1000

Hints for Find the Substring With Maximum Cost

  1. Hint 1

    First turn s into an array of numbers: the value of each letter.

  2. Hint 2

    Now you want the maximum sum of a contiguous subarray, where the empty subarray (sum 0) is allowed.

  3. 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

  1. Build cost[26] with cost[c] = c + 1, then overwrite cost[chars[i]] = vals[i] for each i.
  2. Scan s keeping cur, the best cost of a substring ending at the current position (or empty): cur = max(0, cur + cost[s[i]]).
  3. 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 chars keep their alphabet position as value.
  • chars[i] pairs with vals[i] by index — build the lookup table once instead of searching chars for 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 best

Java

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.

All 1199 arrays problems · the whole catalogue

Learn the technique: Arrays · Strings