Find the Substring With Maximum Cost - Solution & Explanation
Problem Statement
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'is1, the value of'b'is2, and so on. The value of'z'is26.
- For example, the value of
- Otherwise, assuming
iis 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 <= 105sconsist of lowercase English letters.1 <= chars.length <= 26charsconsist 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.
This C solution first creates a mapping of character costs using the charValues array where each character's default cost is its one-based alphabetical index. Then, it updates the costs of the specific characters in chars using their corresponding values from vals. The main loop calculates a running maximum cost similar to Kadane's algorithm, resetting the current cost whenever it becomes negative, and updating the global maximum cost whenever a higher value is encountered.
Complexity
Time Complexity: O(n), where n is the length of string s, because we traverse through the string once.
Space Complexity: O(1), since we use a constant amount of extra space for character mapping and variables.
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.
The C solution initializes an array with alphabet values, updates it for specific characters, and precomputes values for string s. A second pass sums using Kadane-like logic to ascertain maximum costs iteratively.
Complexity
Time Complexity: O(n), due to traversal for creation and evaluation of values.
Space Complexity: O(n), extra space for precomputed values.
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.
Code
Python
Java
C++
Go
TypeScript
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.
Code
Python
Java
C++
Go
TypeScript
Complexity Comparison
| Approach | Complexity |
|---|---|
| Approach 1: Sliding Window using Kadane's Algorithm | Time Complexity: O(n), where n is the length of string |
| Approach 2: Precompute Character Values and Scan | Time Complexity: O(n), due to traversal for creation and evaluation of values. |
| Prefix sum + Maintain the minimum prefix sum | — |
| Convert to the maximum subarray sum problem | — |
Detailed 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. |
Video Solution
Leetcode 2606: Find the Substring With Maximum Cost • Algorithms Casts • 337 views views
Watch 9 more video solutions →Frequently Asked Questions
Is Find the Substring With Maximum Cost easy or hard?
Find the Substring With Maximum Cost Python/Java solution
How to solve Find the Substring With Maximum Cost in O(n)?
What is the best approach for Find the Substring With Maximum Cost?
Is Find the Substring With Maximum Cost asked at Google/Amazon/Meta?
What data structure is used in Find the Substring With Maximum Cost?
What is the time complexity of Find the Substring With Maximum Cost?
Ready to solve this problem?
Practice Find the Substring With Maximum Cost with our built-in code editor and test cases.
Practice on FleetCode