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

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Find the Substring With Maximum Cost

Difficulty: Medium

Problem Description

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 based on whether it is in chars or by its 1-indexed position in the alphabet. Return the maximum cost among all substrings of the string s.

Key Insights

  • Each character in the string s has a cost associated with it based on its presence in chars or its position in the alphabet.
  • The problem can be approached using a sliding window technique or a variation of Kadane's algorithm to find the maximum sum of a contiguous subarray.
  • We need to efficiently calculate the cost of each character while iterating through the string s.

Space and Time Complexity

Time Complexity: O(n), where n is the length of string s.
Space Complexity: O(1), as we are using a fixed amount of extra space regardless of input size.

Solution

The solution involves iterating through each character in the string s and calculating its cost. We maintain a current sum of the costs, and if this sum becomes negative, we reset it to zero since we only care about the maximum cost of contiguous substrings. We also keep track of the maximum cost encountered. A hash map (dictionary) can be used to store the values of characters in chars for quick lookup.

Code Solutions

def maximumCostSubstring(s: str, chars: str, vals: List[int]) -> int:
    # Create a mapping of characters in chars to their corresponding values
    value_map = {char: val for char, val in zip(chars, vals)}
    
    max_cost = 0
    current_cost = 0
    
    for char in s:
        # Calculate the value of the current character
        char_value = value_map.get(char, ord(char) - ord('a') + 1)
        current_cost += char_value
        
        # Update max_cost if current_cost is greater
        max_cost = max(max_cost, current_cost)
        
        # Reset current_cost if it goes below 0
        if current_cost < 0:
            current_cost = 0
            
    return max_cost
← Back to All Questions