Watch 10 video solutions for Find the Substring With Maximum Cost, a medium level problem involving Array, Hash Table, String. This walkthrough by Algorithms Casts has 327 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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:
chars, then its value is its corresponding position (1-indexed) in the alphabet.
'a' is 1, the value of 'b' is 2, and so on. The value of 'z' is 26.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 <= 105s consist of lowercase English letters.1 <= chars.length <= 26chars consist of distinct lowercase English letters.vals.length == chars.length-1000 <= vals[i] <= 1000Problem 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 | 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. |