2606 Find Substring With Maximum Cost Solution

Q: Is Find the Substring With Maximum Cost easy or hard?

Find the Substring With Maximum Cost is rated Medium difficulty on LeetCode. The challenge is recognizing that the problem reduces to the maximum subarray problem after assigning numeric values to characters. Once that insight is clear, the implementation is straightforward.

Q: Find the Substring With Maximum Cost Python/Java solution

Python and Java implementations both follow the same idea: build a lookup table for character costs, iterate through the string, and apply Kadane’s algorithm to track the maximum substring sum. The runtime is O(n) and the code is usually under 20 lines.

Q: How to solve Find the Substring With Maximum Cost in O(n)?

First assign each character its cost using a 26-length array or hash map. Then scan the string while maintaining a running substring sum. If the running sum becomes negative, reset it to zero and continue. Track the maximum sum during the scan to obtain the highest-cost substring in linear time.

Q: What is the best approach for Find the Substring With Maximum Cost?

The optimal approach uses Kadane’s algorithm (maximum subarray) after converting each character to its numeric cost. Iterate through the string, maintain a running sum, reset the sum when it becomes negative, and track the maximum value seen. This solves the problem in O(n) time and O(1) space.

Q: Is Find the Substring With Maximum Cost asked at Google/Amazon/Meta?

Problems based on the maximum subarray pattern frequently appear in interviews at companies like Amazon, Google, and Meta. Variations often combine strings with Kadane’s algorithm or dynamic programming concepts. Recognizing the reduction to maximum subarray is the key skill interviewers test.

Q: What data structure is used in Find the Substring With Maximum Cost?

The solution typically uses a small lookup structure such as an array of size 26 or a hash table to store character values. After mapping characters to integers, the algorithm performs a linear scan using dynamic programming principles from Kadane’s algorithm.

Q: What is the time complexity of Find the Substring With Maximum Cost?

The optimal solution runs in O(n) time where n is the length of the string. Each character is processed exactly once during the Kadane-style scan. The space complexity is O(1) because only a small fixed-size lookup table for character values is required.

The problem

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 <= 10⁵
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

Approach overview

Problem Overview: You receive a string s and a custom value mapping for some characters. Every character not explicitly mapped gets its default alphabetical value (a = 1, b = 2, ...). The goal is to find a substring whose total character value is as large as possible. Negative character values may appear, so the optimal substring may skip sections of the string entirely.

Approach 1: Sliding Window using Kadane's Algorithm (O(n) time, O(1) space)

This problem reduces directly to the classic maximum subarray problem. First compute the value of each character using a small lookup structure such as an array or hash table. Then iterate through the string while maintaining a running sum of the current substring. If the running sum becomes negative, reset it to zero because continuing would only reduce future totals. This is the core idea of Kadane’s algorithm from dynamic programming. During the scan, keep track of the maximum value seen so far. The algorithm touches each character once, giving O(n) time and constant extra space.

The sliding window interpretation is intuitive: extend the window while the accumulated cost is beneficial, and drop the prefix whenever the sum becomes negative. This ensures the window always represents the best possible substring ending at the current position. Since substring costs depend only on character values, no additional data structures are required.

Approach 2: Precompute Character Values and Linear Scan (O(n) time, O(1) space)

Another way to structure the solution is to separate the value computation from the scanning step. Start by building a fixed array of size 26 that stores the cost of every lowercase letter. Initialize it with the default alphabetical values, then override entries using the provided mapping. After this preprocessing step, convert each character in the string to its numeric value and perform a single linear scan to track the best substring sum.

The scanning step again mirrors Kadane’s algorithm: maintain a running sum, reset when it becomes negative, and update the maximum result. The difference is organizational rather than algorithmic. Precomputing the lookup table removes repeated conditional checks and keeps the main loop very tight. This approach works well in languages where array indexing is faster than repeated string or map operations.

Recommended for interviews: Interviewers typically expect the Kadane-based solution. A brute-force substring check would take O(n²) time and shows baseline understanding, but recognizing the maximum subarray pattern demonstrates strong algorithmic intuition. Implementing Kadane’s algorithm with a character-value lookup produces the optimal O(n) time solution with minimal code.

Approach 1: Approach 1: Sliding Window using Kadane's Algorithm

We can apply a modified version of Kadane's algorithm to solve this problem. The primary idea here is to traverse through the string while maintaining the running maximum cost ending at each position. This approach utilizes a hashmap to store the values of the characters given in the chars array. For each character in the input string s, we determine its cost based on whether it is present in the chars string or based on its alphabetical index, if not present. By maintaining a running sum of these values and resetting the sum whenever it becomes negative, we can track the maximum sum of any substring experienced up to any point in the string.

Python

def maxCost(s, chars, vals):
    char_values = {chars[i]: vals[i] for i in range(len(chars))}
    max_cost = 0
    current_cost = 0
    for c in s:
        char_value = char_values.get(c, ord(c) - ord('a') + 1)
        current_cost += char_value
        if current_cost < 0:
            current_cost = 0
        if current_cost > max_cost:
            max_cost = current_cost
    return max_cost

# Example usage
print(maxCost("adaa", "d", [-1000]))

Java

import java.util.HashMap;

public class MaxCostSubstring {
    public int maxCost(String s, String chars, int[] vals) {
        HashMap<Character, Integer> charValueMap = new HashMap<>();
        for (int i = 0; i < chars.length(); i++) {
            charValueMap.put(chars.charAt(i), vals[i]);
        }
        int maxCost = 0, currentCost = 0;
        for (char c : s.toCharArray()) {
            int charVal = charValueMap.getOrDefault(c, c - 'a' + 1);
            currentCost += charVal;
            if (currentCost < 0) currentCost = 0;
            if (currentCost > maxCost) maxCost = currentCost;
        }
        return maxCost;
    }

    public static void main(String[] args) {
        MaxCostSubstring solver = new MaxCostSubstring();
        System.out.println(solver.maxCost("adaa", "d", new int[]{-1000}));
    }
}

C++

#include <iostream>
#include <vector>
#include <unordered_map>
#include <climits>
using namespace std;

int maxCost(string s, string chars, vector<int>& vals) {
    unordered_map<char, int> charValueMap;
    for (size_t i = 0; i < chars.size(); ++i) {
        charValueMap[chars[i]] = vals[i];
    }
    int maxCost = 0, currentCost = 0;
    for (char c : s) {
        int charVal = (charValueMap.count(c)) ? charValueMap[c] : (c - 'a' + 1);
        currentCost = max(charVal, currentCost + charVal);
        maxCost = max(maxCost, currentCost);
        if (currentCost < 0) currentCost = 0;
    }
    return maxCost;
}

int main() {
    string s = "adaa";
    string chars = "d";
    vector<int> vals = {-1000};
    cout << maxCost(s, chars, vals) << endl;
    return 0;
}

JavaScript

function maxCost(s, chars, vals) {
  let charValues = {};
  for (let i = 0; i < chars.length; i++) {
    charValues[chars[i]] = vals[i];
  }
  let maxCost = 0;
  let currentCost = 0;
  for (let c of s) {
    let charVal = charValues[c] !== undefined ? charValues[c] : c.charCodeAt(0) - 'a'.charCodeAt(0) + 1;
    currentCost += charVal;
    if (currentCost < 0) currentCost = 0;
    maxCost = Math.max(maxCost, currentCost);
  }
  return maxCost;
}

console.log(maxCost("adaa", "d", [-1000]));

#include <stdio.h>
#include <string.h>
#include <limits.h>

int maxCost(char* s, char* chars, int* vals, int charsSize) {
    int charValues[26];
    for (int i = 0; i < 26; ++i) {
        charValues[i] = i + 1;
    }
    for (int i = 0; i < charsSize; ++i) {
        charValues[chars[i] - 'a'] = vals[i];
    }
    
    int maxCost = 0;
    int currentCost = 0;
    for (int i = 0; s[i] != '\0'; ++i) {
        int charValue = charValues[s[i] - 'a'];
        currentCost = (currentCost + charValue > charValue) ? currentCost + charValue : charValue;
        if (currentCost < 0) currentCost = 0;
        if (currentCost > maxCost) maxCost = currentCost;
    }
    return maxCost;
}

int main() {
    char s[] = "adaa";
    char chars[] = "d";
    int vals[] = {-1000};
    int result = maxCost(s, chars, vals, 1);
    printf("%d\n", result);
    return 0;
}

using System;
using System.Collections.Generic;

public class MaxCostSubstring {
    public int MaxCost(string s, string chars, int[] vals) {
        Dictionary<char, int> charValues = new Dictionary<char, int>();
        for (int i = 0; i < chars.Length; i++) {
            charValues[chars[i]] = vals[i];
        }
        int maxCost = 0, currentCost = 0;
        foreach (char c in s) {
            int charVal = charValues.ContainsKey(c) ? charValues[c] : (c - 'a' + 1);
            currentCost += charVal;
            if (currentCost < 0) currentCost = 0;
            if (currentCost > maxCost) maxCost = currentCost;
        }
        return maxCost;
    }

    public static void Main() {
        MaxCostSubstring solver = new MaxCostSubstring();
        Console.WriteLine(solver.MaxCost("adaa", "d", new int[]{-1000}));
    }
}

The Python solution utilizes a dictionary for character value storage, mapping input characters to their specified values. Iterating through each character in string s, it computes a running cost and updates the maximum potential cost using Python's dictionary function get for default alpha-index lookup.

Complexity

Time Complexity: O(n), n being the length of string s.
Space Complexity: O(1), extra lookup and iteration space is fixed.

Try this approach in the editor

Approach 2: Approach 2: Precompute Character Values and Scan

In this approach, the initial step is to precompute the cost of each character in the string s before running through it. This involves constructing a list or array that contains precomputed costs for every position in the string based on the chars string and the vals array. Once we have the precomputed values, we can perform a single scan of the string with similar logic to a prefix sum array method, updating our current and maximal cost values as we progress. This approach emphasizes separating computation of values and calculation steps for clarity.

Python

def maxCostPrecompute(s, chars, vals):
    char_values = {chars[i]: vals[i] for i in range(len(chars))}
    precomputed_vals = []
    for c in s:
        precomputed_vals.append(char_values.get(c, ord(c) - ord('a') + 1))

    max_cost = 0
    current_cost = 0
    for val in precomputed_vals:
        current_cost = max(val, current_cost + val)
        if current_cost < 0:
            current_cost = 0
        max_cost = max(max_cost, current_cost)
    return max_cost

# Example usage
print(maxCostPrecompute("adaa", "d", [-1000]))

Java

import java.util.HashMap;

public class MaxCostSubstringPrecompute {
    public int maxCostPrecompute(String s, String chars, int[] vals) {
        int[] charValues = new int[26];
        for (int i = 0; i < 26; i++) {
            charValues[i] = i + 1;
        }
        for (int i = 0; i < chars.length(); i++) {
            charValues[chars.charAt(i) - 'a'] = vals[i];
        }
        int[] precomputedVals = new int[s.length()];
        for (int i = 0; i < s.length(); i++) {
            precomputedVals[i] = charValues[s.charAt(i) - 'a'];
        }
        int maxCost = 0, currentCost = 0;
        for (int val : precomputedVals) {
            currentCost = Math.max(val, currentCost + val);
            if (currentCost < 0) currentCost = 0;
            maxCost = Math.max(maxCost, currentCost);
        }
        return maxCost;
    }

    public static void main(String[] args) {
        MaxCostSubstringPrecompute solver = new MaxCostSubstringPrecompute();
        System.out.println(solver.maxCostPrecompute("adaa", "d", new int[]{-1000}));
    }
}

C++

#include <iostream>
#include <vector>
#include <unordered_map>
using namespace std;

int maxCostPrecompute(string s, string chars, vector<int>& vals) {
    vector<int> charValues(26);
    for (int i = 0; i < 26; ++i) {
        charValues[i] = i + 1;
    }
    for (size_t i = 0; i < chars.size(); ++i) {
        charValues[chars[i] - 'a'] = vals[i];
    }
    vector<int> precomputedVals(s.size());
    for (size_t i = 0; i < s.size(); ++i) {
        precomputedVals[i] = charValues[s[i] - 'a'];
    }
    int maxCost = 0, currentCost = 0;
    for (int val : precomputedVals) {
        currentCost = max(val, currentCost + val);
        if (currentCost < 0) currentCost = 0;
        maxCost = max(maxCost, currentCost);
    }
    return maxCost;
}

int main() {
    string s = "adaa";
    string chars = "d";
    vector<int> vals = {-1000};
    cout << maxCostPrecompute(s, chars, vals) << endl;
    return 0;
}

JavaScript

function maxCostPrecompute(s, chars, vals) {
  let charValues = {};
  for (let i = 0; i < chars.length; i++) {
    charValues[chars[i]] = vals[i];
  }

  let precomputedVals = [];
  for (let c of s) {
    precomputedVals.push(charValues[c] !== undefined ? charValues[c] : c.charCodeAt(0) - 'a' + 1);
  }

  let maxCost = 0;
  let currentCost = 0;
  for (let val of precomputedVals) {
    currentCost = Math.max(val, currentCost + val);
    if (currentCost < 0) currentCost = 0;
    maxCost = Math.max(maxCost, currentCost);
  }
  return maxCost;
}

console.log(maxCostPrecompute("adaa", "d", [-1000]));

#include <stdio.h>
#include <string.h>

int maxCostPrecompute(char* s, char* chars, int* vals, int charsSize) {
    int n = strlen(s);
    int charValues[26];
    for (int i = 0; i < 26; ++i) {
        charValues[i] = i + 1;
    }
    for (int i = 0; i < charsSize; ++i) {
        charValues[chars[i] - 'a'] = vals[i];
    }
    int precomputedVals[n];
    for (int i = 0; i < n; ++i) {
        precomputedVals[i] = charValues[s[i] - 'a'];
    }
    int maxCost = 0, currentCost = 0;
    for (int i = 0; i < n; ++i) {
        currentCost = (currentCost + precomputedVals[i] > precomputedVals[i]) ? currentCost + precomputedVals[i] : precomputedVals[i];
        if (currentCost < 0) currentCost = 0;
        if (currentCost > maxCost) maxCost = currentCost;
    }
    return maxCost;
}

int main() {
    char s[] = "adaa";
    char chars[] = "d";
    int vals[] = {-1000};
    int result = maxCostPrecompute(s, chars, vals, 1);
    printf("%d\n", result);
    return 0;
}

using System;
using System.Collections.Generic;

public class MaxCostSubstringPrecompute {
    public int MaxCostPrecompute(string s, string chars, int[] vals) {
        int[] charValues = new int[26];
        for (int i = 0; i < 26; i++) {
            charValues[i] = i + 1;
        }
        for (int i = 0; i < chars.Length; i++) {
            charValues[chars[i] - 'a'] = vals[i];
        }
        int[] precomputedVals = new int[s.Length];
        for (int i = 0; i < s.Length; i++) {
            precomputedVals[i] = charValues[s[i] - 'a'];
        }
        int maxCost = 0, currentCost = 0;
        foreach (int val in precomputedVals) {
            currentCost = Math.Max(val, currentCost + val);
            if (currentCost < 0) currentCost = 0;
            maxCost = Math.Max(maxCost, currentCost);
        }
        return maxCost;
    }

    public static void Main() {
        MaxCostSubstringPrecompute solver = new MaxCostSubstringPrecompute();
        Console.WriteLine(solver.MaxCostPrecompute("adaa", "d", new int[]{-1000}));
    }
}

In the Python function, all character costs are precomputed ahead followed by a single traversal using controlled-running sum maximization. By separating the value computation from cost accumulation, the solution strategically divides concerns for clarity.

Complexity

Time Complexity: O(n), similarly characterized by precomputation and evaluation runs.
Space Complexity: O(n), for storing precomputed character values.

Try this approach in the editor

Approach 3: 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, tot-mi. We update the answer ans=max(ans,tot-mi) 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.

TypeScript

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

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
}

Try this approach in the editor

Approach 4: 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.

TypeScript

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

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
}

Try this approach in the editor

Complexity comparison

Approach	Complexity
Approach 1: Sliding Window using Kadane's Algorithm	Time Complexity: O(n), n being the length of string `s`. Space Complexity: O(1), extra lookup and iteration space is fixed.
Approach 2: Precompute Character Values and Scan	Time Complexity: O(n), similarly characterized by precomputation and evaluation runs. Space Complexity: O(n), for storing precomputed character values.
Prefix sum + Maintain the minimum prefix sum	–
Convert to the maximum subarray sum problem	–

Complexity analysis

Approach	Time	Space	When to Use
Sliding Window using Kadane's Algorithm	O(n)	O(1)	Best general solution. Recognizes the maximum subarray pattern and works for any string length.
Precompute Character Values and Scan	O(n)	O(1)	Useful when you want a clean implementation with fast array lookups for character costs.

Frequently asked questions

Is Find the Substring With Maximum Cost easy or hard?

Find the Substring With Maximum Cost is rated Medium difficulty on LeetCode. The challenge is recognizing that the problem reduces to the maximum subarray problem after assigning numeric values to characters. Once that insight is clear, the implementation is straightforward.

Find the Substring With Maximum Cost Python/Java solution

Python and Java implementations both follow the same idea: build a lookup table for character costs, iterate through the string, and apply Kadane’s algorithm to track the maximum substring sum. The runtime is O(n) and the code is usually under 20 lines.

How to solve Find the Substring With Maximum Cost in O(n)?

First assign each character its cost using a 26-length array or hash map. Then scan the string while maintaining a running substring sum. If the running sum becomes negative, reset it to zero and continue. Track the maximum sum during the scan to obtain the highest-cost substring in linear time.

What is the best approach for Find the Substring With Maximum Cost?

The optimal approach uses Kadane’s algorithm (maximum subarray) after converting each character to its numeric cost. Iterate through the string, maintain a running sum, reset the sum when it becomes negative, and track the maximum value seen. This solves the problem in O(n) time and O(1) space.

Is Find the Substring With Maximum Cost asked at Google/Amazon/Meta?

Problems based on the maximum subarray pattern frequently appear in interviews at companies like Amazon, Google, and Meta. Variations often combine strings with Kadane’s algorithm or dynamic programming concepts. Recognizing the reduction to maximum subarray is the key skill interviewers test.

What data structure is used in Find the Substring With Maximum Cost?

The solution typically uses a small lookup structure such as an array of size 26 or a hash table to store character values. After mapping characters to integers, the algorithm performs a linear scan using dynamic programming principles from Kadane’s algorithm.

What is the time complexity of Find the Substring With Maximum Cost?

The optimal solution runs in O(n) time where n is the length of the string. Each character is processed exactly once during the Kadane-style scan. The space complexity is O(1) because only a small fixed-size lookup table for character values is required.

Find the Substring With Maximum Cost solution and explanation

The problem

Approach overview

Approach 1: Approach 1: Sliding Window using Kadane's Algorithm

Approach 2: Approach 2: Precompute Character Values and Scan

Approach 3: Prefix sum + Maintain the minimum prefix sum

Approach 4: Convert to the maximum subarray sum problem

Complexity comparison

Complexity analysis

Frequently asked questions

Comments

Find the Substring With Maximum Cost solution and explanation

The problem

Approach overview

Approach 1: Approach 1: Sliding Window using Kadane's Algorithm

Approach 2: Approach 2: Precompute Character Values and Scan

Approach 3: Prefix sum + Maintain the minimum prefix sum

Approach 4: Convert to the maximum subarray sum problem

Complexity comparison

Complexity analysis

Frequently asked questions

Comments

Related problems