Find the substring with maximum cost

Array Hash Table String Dynamic Programming

57.8% acceptance

Feb 25, 2026

394

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.

Solution

Rust

Time O(n)

Space O(1)

LeetCode

solution.rs

impl Solution {
  pub fn maximum_cost_substring(s: String, chars: String, vals: Vec<i32>) -> i32 {
    let mut val_map = [0i32; 26];
    // Default: position in alphabet (1-indexed)
    for i in 0..26 {
      val_map[i] = (i + 1) as i32;
    }
    for (c, &v) in chars.bytes().zip(vals.iter()) {
      val_map[(c - b'a') as usize] = v;
    }

    // Kadane's algorithm
    let mut max_cost = 0i32;
    let mut cur = 0i32;
    for b in s.bytes() {
      cur += val_map[(b - b'a') as usize];
      if cur < 0 {
        cur = 0;
      }
      if cur > max_cost {
        max_cost = cur;
      }
    }
    max_cost
  }
}