Scale Engineer

Find the Substring With Maximum Cost

Med
#2386Time: O(N^2), where N is the length of the string `s`. The two nested loops result in a quadratic number of operations relative to the input string size. The pre-computation step takes constant time.Space: O(1). We only use an array of size 26 to store character values, which is considered constant space.1 company
Patterns
Dynamic Programming
Data structures
ArrayHash TableString
Companies
josh technology

Prompt

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:

  • If the character is not in the string chars, then its value is its corresponding position (1-indexed) in the alphabet.
    • For example, the value of 'a' is 1, the value of 'b' is 2, and so on. The value of 'z' is 26.
  • Otherwise, assuming 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 <= 105
  • s consist of lowercase English letters.
  • 1 <= chars.length <= 26
  • chars consist of distinct lowercase English letters.
  • vals.length == chars.length
  • -1000 <= vals[i] <= 1000

Approaches

2 approaches with complexity analysis and trade-offs.

This approach systematically considers every possible substring of the input string s. For each substring, it calculates its cost by summing the values of its characters and then updates the maximum cost found so far. While straightforward, it is not efficient for large strings.

Algorithm

  • Create a value map charValues for all 26 lowercase letters.
  • Initialize charValues with default alphabet positions (1-26).
  • Update charValues using the chars and vals input.
  • Initialize maxCost = 0 to account for the empty substring.
  • Iterate through the string s with a start index i from 0 to s.length() - 1:
    • Initialize currentCost = 0 for the substring starting at i.
    • Iterate with an end index j from i to s.length() - 1:
      • Get the value of s.charAt(j) from charValues.
      • Add this value to currentCost.
      • Update maxCost = max(maxCost, currentCost).
  • Return maxCost.

Walkthrough

First, we need a way to quickly find the value of any character. We can pre-compute these values and store them in an array. We'll create an integer array charValues of size 26, initialized with default alphabet values (1 for 'a', 2 for 'b', etc.). Then, we update this array using the chars string and vals array for any custom values.

The main part of the algorithm involves two nested loops to generate all substrings. The outer loop selects a starting point i, and the inner loop selects an ending point j. For each substring s.substring(i, j+1), we calculate its cost. To do this efficiently within the loops, we maintain a currentCost for substrings starting at i. As we extend the substring by incrementing j, we add the value of the new character s.charAt(j) to currentCost.

We maintain a global variable maxCost, initialized to 0 (to handle the empty substring case), and continuously update it with the currentCost if the currentCost is greater. After checking all O(N^2) substrings, maxCost will hold the final answer.

class Solution {    public int maximumCostSubstring(String s, String chars, int[] vals) {        int[] charValues = new int[26];        for (int i = 0; i < 26; i++) {            charValues[i] = i + 1;        }         for (int i = 0; i < chars.length(); i++) {            charValues[chars.charAt(i) - 'a'] = vals[i];        }         int maxCost = 0;        int n = s.length();         for (int i = 0; i < n; i++) {            int currentCost = 0;            for (int j = i; j < n; j++) {                currentCost += charValues[s.charAt(j) - 'a'];                maxCost = Math.max(maxCost, currentCost);            }        }         return maxCost;    }}

Complexity

Time

O(N^2), where N is the length of the string `s`. The two nested loops result in a quadratic number of operations relative to the input string size. The pre-computation step takes constant time.

Space

O(1). We only use an array of size 26 to store character values, which is considered constant space.

Trade-offs

Pros

  • Simple to understand and implement.

  • Correctly solves the problem for small inputs.

Cons

  • This approach is inefficient and will likely result in a 'Time Limit Exceeded' error for large inputs, as its time complexity is quadratic.

Solutions

class Solution { public int maximumCostSubstring ( String s , String chars , int [] vals ) { int [] d = new int [ 26 ]; for ( int i = 0 ; i < d . length ; ++ i ) { d [ i ] = i + 1 ; } int m = chars . length (); for ( int i = 0 ; i < m ; ++ i ) { d [ chars . charAt ( i ) - 'a' ] = vals [ i ]; } int ans = 0 , tot = 0 , mi = 0 ; int n = s . length (); for ( int i = 0 ; i < n ; ++ i ) { int v = d [ s . charAt ( i ) - 'a' ]; tot += v ; ans = Math . max ( ans , tot - mi ); mi = Math . min ( mi , tot ); } return ans ; } }

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next →

Next problem