Problem Description

You are given a string s, a string chars containing distinct characters, and an integer array vals that has the same length as chars.

Each character in string s has a value determined by these rules:

• If the character appears in chars at index i, its value is vals[i]
• If the character doesn't appear in chars, its value is its position in the alphabet (1-indexed), where 'a' = 1, 'b' = 2, ..., 'z' = 26

The cost of a substring is the sum of values of all its characters. An empty string has a cost of 0.

Your task is to find the maximum cost among all possible substrings of string s.

For example, if s = "abc", chars = "b", and vals = [-10]:

• Character 'a' is not in chars, so its value is 1
• Character 'b' is in chars at index 0, so its value is vals[0] = -10
• Character 'c' is not in chars, so its value is 3

The possible substrings and their costs would be calculated based on these values, and you need to return the maximum cost found.

The solution uses a prefix sum approach with tracking of the minimum prefix sum seen so far. As we traverse through the string, we calculate the running total and find the maximum cost substring ending at each position by subtracting the minimum prefix sum from the current total.

Intuition

The problem asks for the maximum cost substring, which is essentially asking for the maximum sum of a contiguous subarray after we transform each character to its corresponding value. This is a classic maximum subarray sum problem, similar to Kadane's algorithm.

The key insight is that for any substring from index i to index j, its cost equals prefix_sum[j] - prefix_sum[i-1]. To maximize this value for a substring ending at position j, we need to minimize prefix_sum[i-1].

Think of it this way: as we scan through the string from left to right and calculate the running total (prefix sum), at each position we ask: "What's the maximum cost substring that ends here?" The answer is the current total minus the smallest prefix sum we've seen so far.

Why does this work? Because:

• If we subtract the minimum prefix sum from the current total, we get the maximum possible substring sum ending at the current position
• If the minimum prefix sum is negative, subtracting it actually increases our result
• If the minimum prefix sum is positive, we're finding the best starting point to maximize our substring cost
• If the minimum prefix sum is 0 (initial value), we're taking the entire prefix as our substring

This approach elegantly handles both positive and negative character values. When we have negative values, the algorithm naturally finds the optimal starting point that excludes costly negative prefixes. When all values are positive, it tends to include more characters. The beauty is that by tracking just two values - the running total and the minimum prefix sum seen so far - we can find the maximum cost substring in a single pass through the string.

Learn more about Dynamic Programming patterns.

Solution Approach

The implementation uses a prefix sum technique combined with tracking the minimum prefix sum to find the maximum cost substring efficiently in a single pass.

Step-by-step implementation:

1. Create a value mapping dictionary: First, we create a dictionary d that maps each character in chars to its corresponding value in vals:

   d = {c: v for c, v in zip(chars, vals)}

2. Initialize tracking variables:

   • ans = 0: Stores the maximum cost found so far
   • tot = 0: Maintains the running prefix sum
   • mi = 0: Tracks the minimum prefix sum seen so far

3. Process each character: For each character c in string s:

   • Get character value: Use d.get(c, ord(c) - ord('a') + 1) to retrieve the value

     • If c exists in dictionary d, use its mapped value
     • Otherwise, calculate its alphabetical position: ord(c) - ord('a') + 1

   • Update prefix sum: Add the character's value to the running total:

     tot += v

   • Calculate maximum cost ending here: The maximum cost substring ending at the current position is tot - mi. Update the answer if this is larger:

     ans = max(ans, tot - mi)

   • Update minimum prefix sum: Keep track of the smallest prefix sum seen:

     mi = min(mi, tot)

4. Return the result: After processing all characters, ans contains the maximum cost among all substrings.

Why this works:

• At each position, tot - mi gives us the maximum sum of any substring ending at that position
• By maintaining mi as the minimum prefix sum, we're effectively finding the optimal starting point for our substring
• The algorithm handles negative values naturally - if including certain characters decreases the cost, the minimum prefix sum will adjust accordingly

Time Complexity: O(n) where n is the length of string s - we traverse the string once
Space Complexity: O(k) where k is the length of chars - for storing the dictionary mapping

Example Walkthrough

Let's walk through an example with s = "adaa", chars = "d", and vals = [-1000].

First, we create our value mapping:

• d = {'d': -1000}

Now let's process each character step by step:

Initial state:

• ans = 0 (maximum cost found)
• tot = 0 (running prefix sum)
• mi = 0 (minimum prefix sum seen)

Character 'a' (index 0):

• Value: Not in chars, so value = 1 (position in alphabet)
• tot = 0 + 1 = 1
• Maximum substring ending here: tot - mi = 1 - 0 = 1
• ans = max(0, 1) = 1
• mi = min(0, 1) = 0

Character 'd' (index 1):

• Value: In chars with value = -1000
• tot = 1 + (-1000) = -999
• Maximum substring ending here: tot - mi = -999 - 0 = -999
• ans = max(1, -999) = 1 (keep previous maximum)
• mi = min(0, -999) = -999

Character 'a' (index 2):

• Value: Not in chars, so value = 1
• tot = -999 + 1 = -998
• Maximum substring ending here: tot - mi = -998 - (-999) = 1
• ans = max(1, 1) = 1
• mi = min(-999, -998) = -999

Character 'a' (index 3):

• Value: Not in chars, so value = 1
• tot = -998 + 1 = -997
• Maximum substring ending here: tot - mi = -997 - (-999) = 2
• ans = max(1, 2) = 2
• mi = min(-999, -997) = -999

Result: The maximum cost is 2, which corresponds to the substring "aa" (from index 2 to 3).

The key insight here is that by tracking the minimum prefix sum (-999 after including 'd'), we can effectively "cut off" the expensive prefix when calculating the maximum substring. When we compute tot - mi at the last position, we're essentially asking: "What if we started our substring right after the character 'd'?" This gives us the substring "aa" with cost 2.

Solution Implementation

Time and Space Complexity

The time complexity is O(n), where n is the length of the string s. This is because the algorithm iterates through each character in the string exactly once, and for each character, it performs constant-time operations: dictionary lookup with d.get(), arithmetic operations for calculating tot, and comparisons for updating ans and mi.

The space complexity is O(C), where C is the size of the character set used in the chars parameter. In this problem, since we're dealing with lowercase English letters, C can be at most 26. The dictionary d stores at most C key-value pairs (one for each unique character in chars). The remaining variables (ans, tot, mi, and v) use constant space O(1), so the overall space complexity is dominated by the dictionary storage, resulting in O(C) or O(26) which simplifies to O(1) constant space.

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Forgetting to Handle Empty Substrings

The problem explicitly states that an empty string has a cost of 0, which means the answer should never be negative. A common mistake is not initializing max_cost to 0, which could lead to returning negative values when all possible substrings have negative costs.

Incorrect approach:

max_cost = float('-inf')  # Wrong! Could return negative value

Correct approach:

max_cost = 0  # Ensures we never return less than 0 (empty substring)

2. Incorrect Character Value Calculation

A frequent error is miscalculating the default alphabetical position value. Remember that 'a' should map to 1, not 0.

Incorrect approaches:

# Wrong: This gives 'a' = 0, 'b' = 1, etc.
char_value = ord(char) - ord('a')

# Wrong: Using 1-indexed position with 'A' instead of 'a'
char_value = ord(char) - ord('A') + 1

Correct approach:

char_value = ord(char) - ord('a') + 1  # 'a' = 1, 'b' = 2, ..., 'z' = 26

3. Not Initializing min_prefix_sum to 0

The minimum prefix sum should start at 0, representing the empty prefix. Starting with any other value (like float('inf')) would incorrectly calculate the maximum substring cost.

Incorrect approach:

min_prefix_sum = float('inf')  # Wrong! First substring calculation would be incorrect

Correct approach:

min_prefix_sum = 0  # Represents the empty prefix before any characters

4. Updating Variables in Wrong Order

The order of operations matters. You must calculate the maximum cost using the current min_prefix_sum before updating it with the new current_sum.

Incorrect approach:

current_sum += char_value
min_prefix_sum = min(min_prefix_sum, current_sum)  # Updated too early!
max_cost = max(max_cost, current_sum - min_prefix_sum)  # Uses wrong min_prefix_sum

Correct approach:

current_sum += char_value
max_cost = max(max_cost, current_sum - min_prefix_sum)  # Use old min_prefix_sum
min_prefix_sum = min(min_prefix_sum, current_sum)  # Then update for next iteration

5. Assuming All Characters are Lowercase

While the problem typically deals with lowercase letters, it's good practice to validate assumptions or handle edge cases.

Robust approach with validation:

def maximumCostSubstring(self, s: str, chars: str, vals: List[int]) -> int:
    # Validate input (optional but recommended)
    if not s:
        return 0
  
    char_to_value = {char: value for char, value in zip(chars, vals)}
    max_cost = 0
    current_sum = 0
    min_prefix_sum = 0
  
    for char in s:
        # Add validation if needed
        if not char.islower():
            raise ValueError(f"Invalid character: {char}")
      
        char_value = char_to_value.get(char, ord(char) - ord('a') + 1)
        current_sum += char_value
        max_cost = max(max_cost, current_sum - min_prefix_sum)
        min_prefix_sum = min(min_prefix_sum, current_sum)
  
    return max_cost