LeetCode 2606 - Find the Substring With Maximum Cost

LeetCode Problem 2606

Difficulty: 🟡 Medium
Topics: Array, Hash Table, String, Dynamic Programming

Solution

Problem Understanding

The problem asks us to find the substring of a given string s that maximizes a custom cost function. Each character in the string has a value: if it exists in the string chars, its value is taken from the corresponding index in the array vals; if it does not exist in chars, its value is simply its 1-indexed position in the alphabet ('a' = 1, 'b' = 2, ..., 'z' = 26). The goal is to calculate the maximum possible sum of values for any contiguous substring of s.

The inputs are:

• s: a string of lowercase letters, up to length 10^5.
• chars: a string of distinct lowercase letters, at most length 26.
• vals: an array of integers corresponding to chars.

The output is a single integer, the maximum cost among all substrings of s. Notably, the empty substring has a cost of 0, which can be the maximum if all characters in s are very negative.

Constraints indicate that s can be large, so any solution worse than O(n) or O(n log n) will likely be too slow. Key edge cases include: all characters negative, all characters positive, s consisting entirely of characters not in chars, and s consisting entirely of characters in chars.

Approaches

The naive approach is brute force: consider every possible substring of s, compute its cost by summing character values, and track the maximum. This is correct because it checks all possible substrings. However, its complexity is O(n^2) for n = length of s, which is infeasible for n = 10^5.

The optimal approach leverages the insight that we are effectively finding the maximum sum subarray problem after mapping each character to its cost. Once each character has a numeric value, the problem reduces to Kadane's algorithm: iterating through the array of costs, maintaining a running sum, and resetting it to zero if it becomes negative. The maximum running sum encountered is the answer.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n^2)	O(1)	Iterate all substrings, sum their costs, track max
Optimal	O(n)	O(1)	Map characters to costs, use Kadane's algorithm

Algorithm Walkthrough

1. Initialize a dictionary char_to_val mapping characters in chars to their corresponding vals.
2. For characters not in chars, define their value as ord(c) - ord('a') + 1.
3. Initialize two variables: max_cost = 0 and current_sum = 0.
4. Iterate through each character c in s.

• Look up its value in char_to_val if present, otherwise use its alphabet value.
• Add the value to current_sum.
• If current_sum drops below zero, reset it to zero because continuing would decrease the maximum sum.
• Update max_cost to be the maximum of max_cost and current_sum.

5. After finishing the iteration, return max_cost.

Why it works: Kadane's algorithm guarantees that the maximum sum of a contiguous subarray is found because it tracks the maximum running sum and discards subarrays that would decrease potential maxima. Mapping characters to their values transforms the substring problem into a numeric array problem.

Python Solution

from typing import List

class Solution:
    def maximumCostSubstring(self, s: str, chars: str, vals: List[int]) -> int:
        char_to_val = {chars[i]: vals[i] for i in range(len(chars))}
        max_cost = 0
        current_sum = 0
        
        for c in s:
            val = char_to_val.get(c, ord(c) - ord('a') + 1)
            current_sum += val
            if current_sum < 0:
                current_sum = 0
            max_cost = max(max_cost, current_sum)
        
        return max_cost

The Python implementation first builds the lookup dictionary for constant-time value retrieval. Then it applies Kadane's algorithm: updating the running sum and maximum sum iteratively. Using ord(c) - ord('a') + 1 handles characters not in chars. Edge cases like all negative costs are naturally handled by resetting current_sum to zero.

Go Solution

func maximumCostSubstring(s string, chars string, vals []int) int {
    charToVal := make(map[rune]int)
    for i, c := range chars {
        charToVal[c] = vals[i]
    }

    maxCost := 0
    currentSum := 0

    for _, c := range s {
        val, exists := charToVal[c]
        if !exists {
            val = int(c - 'a' + 1)
        }
        currentSum += val
        if currentSum < 0 {
            currentSum = 0
        }
        if currentSum > maxCost {
            maxCost = currentSum
        }
    }

    return maxCost
}

The Go solution mirrors Python, using a map[rune]int for character values. The main differences are type casting for rune arithmetic and explicit existence checks with the exists boolean.

Worked Examples

Example 1: s = "adaa", chars = "d", vals = [-1000]

i	c	val	current_sum	max_cost
0	a	1	1	1
1	d	-1000	1 - 1000 = -999	1 → reset current_sum = 0
2	a	1	1	1
3	a	1	2	2

Maximum cost: 2

Example 2: s = "abc", chars = "abc", vals = [-1,-1,-1]

i	c	val	current_sum	max_cost
0	a	-1	-1 → reset 0	0
1	b	-1	-1 → reset 0	0
2	c	-1	-1 → reset 0	0

Maximum cost: 0

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n)	Iterate over string once, O(1) lookup for each character
Space	O(m)	Map stores at most 26 characters, negligible

The time complexity is linear in the length of s due to a single pass. The space complexity is small because chars is limited to 26 characters, so the map remains constant-size.

Test Cases

# Provided examples
assert Solution().maximumCostSubstring("adaa", "d", [-1000]) == 2  # maximum substring "aa"
assert Solution().maximumCostSubstring("abc", "abc", [-1,-1,-1]) == 0  # empty substring

# Edge cases
assert Solution().maximumCostSubstring("aaaaa", "", []) == 15  # all 'a's with default value 1, max substring entire string
assert Solution().maximumCostSubstring("zxy", "x", [-100]) == 51  # z=26, x=-100, y=25, max=26+25=51
assert Solution().maximumCostSubstring("abcd", "abcd", [1,2,3,4]) == 10  # sum of all values
assert Solution().maximumCostSubstring("abcd", "abcd", [-1,-2,-3,-4]) == 0  # all negative, max is empty substring

Test	Why
"adaa"	Mix of negative and positive, verifies substring selection
"abc" negative	All negative values, confirms empty substring handling
"aaaaa"	All positive default values, full string sum
"zxy"	Mixed default and custom negative, ensures correct max choice
"abcd" positive	Sum of all mapped values
"abcd" negative	All negative, checks zero return

Edge Cases

1. All negative values: When every character has a negative cost, the maximum substring is empty. This is handled by initializing max_cost to zero and resetting current_sum when negative.
2. Characters not in chars: Characters with default alphabet values must be handled correctly. By using ord(c) - ord('a') + 1 in Python and int(c - 'a' + 1) in Go, we correctly compute their values.
3. Long string: With s of length up to 10^5, an O(n^2) solution would time out. The linear Kadane-based approach ensures performance scales with large input sizes.
4. Single-character string: A string with one character tests minimal input handling. The algorithm correctly returns either the character's value or zero if negative.
5. All characters positive: When every character value is positive, the maximum substring is the entire string. The algorithm naturally accumulates the sum without resets.