# Find the Substring With Maximum Cost
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/find-the-substring-with-maximum-cost)
Canonical: https://scaleengineer.com/dsa/problems/find-the-substring-with-maximum-cost
**Patterns:** [Dynamic Programming](https://scaleengineer.com/dsa/patterns/dynamic-programming)
**Data structures:** Array, Hash Table, String
**Companies:** [josh technology](https://scaleengineer.com/companies/josh-technology)
---
## Problem
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
## Brute Force by Checking All Substrings
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.
**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.
**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.
### Explanation
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.

```java
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;
    }
}
```
### 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`.

## Dynamic Programming - Kadane's Algorithm
This problem can be efficiently solved by reframing it as the classic 'Maximum Subarray Sum' problem. First, we transform the input string `s` into an array of integers where each integer is the cost of the corresponding character. Then, we apply Kadane's algorithm, a dynamic programming technique, to find the maximum sum of a contiguous subarray in this integer representation in a single pass.
**Time:** O(N), where N is the length of the string `s`. We only need to iterate through the string once. The pre-computation step is O(1) as the alphabet size is fixed. · **Space:** O(1). The space used for the character value map is constant (size 26), and only a few variables are needed for the iteration.
**Pros:** Extremely efficient with a linear time complexity.; Optimal solution for the given constraints.; Uses constant extra space.
**Cons:** The logic might be less intuitive than a direct brute-force approach if one is not familiar with Kadane's algorithm or dynamic programming.
### Explanation
The optimal solution uses Kadane's algorithm. The first step, like in the brute-force approach, is to pre-compute the value for each of the 26 lowercase letters and store them in an array, `charValues`.

The core of the approach is a single loop through the string `s`. We use two variables: `currentCost` to track the sum of the current contiguous substring, and `maxCost` to store the maximum cost found so far. Both are initialized to 0.

As we iterate through `s`, we add the value of the current character to `currentCost`. After this, we update `maxCost` by taking the maximum of its current value and `currentCost`. The key insight of Kadane's algorithm is that if `currentCost` ever drops below zero, it cannot be a beneficial prefix for any subsequent substring. Therefore, if `currentCost` becomes negative, we reset it to 0, effectively starting a new substring from the next character.

This single-pass approach ensures that we find the maximum substring cost in linear time, making it highly efficient.

```java
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 currentCost = 0;

        for (char c : s.toCharArray()) {
            currentCost += charValues[c - 'a'];
            if (currentCost < 0) {
                currentCost = 0;
            }
            maxCost = Math.max(maxCost, currentCost);
        }

        return maxCost;
    }
}
```
### Algorithm
- Create a value map `charValues` for all 26 lowercase letters, initializing with default values (1-26) and then updating with custom values from `chars` and `vals`.
- Initialize `maxCost = 0` and `currentCost = 0`.
- Iterate through each character `c` in the string `s`:
  - Get the value of `c` from `charValues`.
  - Add this value to `currentCost`.
  - If `currentCost` becomes negative, reset it to `0`. This is because a negative-sum prefix will not contribute positively to any future substring sum.
  - Update `maxCost = max(maxCost, currentCost)`.
- After the loop, return `maxCost`.

# Solutions
### Java

```java
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 ; } }
```

### CPP

```cpp
class Solution { public: int maximumCostSubstring ( string s , string chars , vector < int >& vals ) { vector < int > d ( 26 ); iota ( d . begin (), d . end (), 1 ); int m = chars . size (); for ( int i = 0 ; i < m ; ++ i ) { d [ chars [ i ] - 'a' ] = vals [ i ]; } int ans = 0 , tot = 0 , mi = 0 ; for ( char & c : s ) { int v = d [ c - 'a' ]; tot += v ; ans = max ( ans , tot - mi ); mi = min ( mi , tot ); } return ans ; } };
```

### Python

```python
class Solution : def maximumCostSubstring ( self , s : str , chars : str , vals : List [ int ]) -> int : d = { c : v for c , v in zip ( chars , vals )} ans = tot = mi = 0 for c in s : v = d . get ( c , ord ( c ) - ord ( 'a' ) + 1 ) tot += v ans = max ( ans , tot - mi ) mi = min ( mi , tot ) return ans
```