2606. Find the Substring With Maximum Cost LeetCode Solution
In this guide, you will get 2606. Find the Substring With Maximum Cost LeetCode Solution with the best time and space complexity. The solution to Find the Substring With Maximum Cost problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.
Problem Statement of Find the Substring With Maximum Cost
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.
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
Complexity Analysis
Time Complexity: O(n)
Space Complexity: O(26) = O(1)
2606. Find the Substring With Maximum Cost LeetCode Solution in C++
class Solution {
public:
int maximumCostSubstring(string s, string chars, vector<int>& vals) {
int ans = 0;
int cost = 0;
vector<int> costs(26); // costs[i] := the cost of 'a' + i
iota(costs.begin(), costs.end(), 1);
for (int i = 0; i < chars.size(); ++i)
costs[chars[i] - 'a'] = vals[i];
for (const char c : s) {
cost = max(0, cost + costs[c - 'a']);
ans = max(ans, cost);
}
return ans;
}
}; /* code provided by PROGIEZ */
2606. Find the Substring With Maximum Cost LeetCode Solution in Java
class Solution {
public int maximumCostSubstring(String s, String chars, int[] vals) {
int ans = 0;
int cost = 0;
int[] costs = new int[26]; // costs[i] := the cost of 'a' + i
for (int i = 0; i < 26; ++i)
costs[i] = i + 1;
for (int i = 0; i < chars.length(); ++i)
costs[chars.charAt(i) - 'a'] = vals[i];
for (final char c : s.toCharArray()) {
cost = Math.max(0, cost + costs[c - 'a']);
ans = Math.max(ans, cost);
}
return ans;
}
} // code provided by PROGIEZ
2606. Find the Substring With Maximum Cost LeetCode Solution in Python
class Solution:
def maximumCostSubstring(self, s: str, chars: str, vals: list[int]) -> int:
ans = 0
cost = 0
costs = [i for i in range(1, 27)] # costs[i] := the cost of 'a' + i
for c, val in zip(chars, vals):
costs[ord(c) - ord('a')] = val
for c in s:
cost = max(0, cost + costs[ord(c) - ord('a')])
ans = max(ans, cost)
return ans # code by PROGIEZ
