We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Find the Substring With Maximum Cost

Number: 2669

Difficulty: Medium

Paid? No

Companies: Amazon

Problem Description

Given a string s, a string chars that contains distinct characters, and an integer array vals of the same length as chars, determine the maximum cost among all substrings of s. The cost of a substring is defined as the sum of the values of its characters. For any character in s, if it exists in chars, its value is given by vals at the corresponding index; otherwise, its value is its alphabetical position (1-indexed). The cost of an empty substring is 0.

Key Insights

  • Build a hash map of custom values for characters present in chars.
  • For characters not in the hash map, compute their value using their alphabetical position.
  • Convert the problem into finding the maximum subarray sum on the array of computed character values.
  • Kadane's algorithm is an optimal approach for this maximum subarray sum problem.
  • The result should never be negative since the empty substring (cost 0) is always a valid option.

Space and Time Complexity

Time Complexity: O(n), where n is the length of s.
Space Complexity: O(1) additional space (the custom mapping is of constant size due to the limited alphabet).

Solution

The solution involves mapping the characters in chars to their corresponding values using a hash map. As we iterate over string s, we determine each character's value, then apply Kadane's algorithm to find the contiguous substring (subarray) that gives the maximum sum. The algorithm resets the current sum whenever it falls below the current character's value, effectively starting a new substring calculation. This approach efficiently yields the maximum possible cost among all substrings.

Code Solutions

# Python Code
def maximumCostSubstring(s, chars, vals):
    # Create mapping for custom values
    custom_values = {ch: val for ch, val in zip(chars, vals)}
    max_sum = current_sum = 0  # Initialize with the empty substring cost
    for char in s:
        # Get value: use custom mapping if present, otherwise use alphabetical 1-indexed value
        value = custom_values.get(char, ord(char) - ord('a') + 1)
        current_sum = max(value, current_sum + value)  # Kadane's algorithm
        max_sum = max(max_sum, current_sum)
    return max_sum

# Example usage:
print(maximumCostSubstring("adaa", "d", [-1000]))  # Expected Output: 2
print(maximumCostSubstring("abc", "abc", [-1, -1, -1]))  # Expected Output: 0
← Back to All Questions