Question

2606. 找到最大开销的子字符串

English Version

题目描述

给你一个字符串 s ，一个字符 互不相同 的字符串 chars 和一个长度与 chars 相同的整数数组 vals 。

子字符串的开销 是一个子字符串中所有字符对应价值之和。空字符串的开销是 0 。

字符的价值 定义如下：

• 如果字符不在字符串 chars 中，那么它的价值是它在字母表中的位置（下标从 1 开始）。
  • 比方说，'a' 的价值为 1 ，'b' 的价值为 2 ，以此类推，'z' 的价值为 26 。
• 否则，如果这个字符在 chars 中的位置为 i ，那么它的价值就是 vals[i] 。

请你返回字符串 s 的所有子字符串中的最大开销。

 

示例 1：

输入：s = "adaa", chars = "d", vals = [-1000]
输出：2
解释：字符 "a" 和 "d" 的价值分别为 1 和 -1000 。
最大开销子字符串是 "aa" ，它的开销为 1 + 1 = 2 。
2 是最大开销。

示例 2：

输入：s = "abc", chars = "abc", vals = [-1,-1,-1]
输出：0
解释：字符 "a" ，"b" 和 "c" 的价值分别为 -1 ，-1 和 -1 。
最大开销子字符串是 "" ，它的开销为 0 。
0 是最大开销。

 

提示：

• 1 <= s.length <= 105
• s 只包含小写英文字母。
• 1 <= chars.length <= 26
• chars 只包含小写英文字母，且 互不相同 。
• vals.length == chars.length
• -1000 <= vals[i] <= 1000

解法

方法一：前缀和 + 维护前缀和的最小值

我们根据题目描述，遍历字符串 $s$ 的每个字符 $c$，求出其对应的价值 $v$，然后更新当前的前缀和 $tot=tot+v$，那么以 $c$ 结尾的最大开销子字符串的开销为 $tot$ 减去前缀和的最小值 $mi$，即 $tot-mi$，我们更新答案 $ans=max(ans,tot-mi)$，并维护前缀和的最小值 $mi=min(mi,tot)$。

遍历结束后返回答案 $ans$ 即可。

时间复杂度 $O(n)$，空间复杂度 $O(C)$。其中 $n$ 为字符串 $s$ 的长度；而 $C$ 为字符集的大小，本题中 $C=26$。

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

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

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

func maximumCostSubstring(s string, chars string, vals []int) (ans int) {
  d := [26]int{}
  for i := range d {
    d[i] = i + 1
  }
  for i, c := range chars {
    d[c-'a'] = vals[i]
  }
  tot, mi := 0, 0
  for _, c := range s {
    v := d[c-'a']
    tot += v
    ans = max(ans, tot-mi)
    mi = min(mi, tot)
  }
  return
}

function maximumCostSubstring(s: string, chars: string, vals: number[]): number {
  const d: number[] = Array.from({ length: 26 }, (_, i) => i + 1);
  for (let i = 0; i < chars.length; ++i) {
    d[chars.charCodeAt(i) - 97] = vals[i];
  }
  let ans = 0;
  let tot = 0;
  let mi = 0;
  for (const c of s) {
    tot += d[c.charCodeAt(0) - 97];
    ans = Math.max(ans, tot - mi);
    mi = Math.min(mi, tot);
  }
  return ans;
}

方法二：转化为最大子数组和问题

我们可以将每个字符 $c$ 的价值 $v$ 看作是一个整数，那么题目实际上转化为求最大子数组和问题。

我们用变量 $f$ 维护以当前字符 $c$ 结尾的最大开销子字符串的开销，每次遍历到一个字符 $c$，更新 $f=max(f, 0) + v$，然后更新答案 $ans=max(ans,f)$ 即可。

时间复杂度 $O(n)$，空间复杂度 $O(C)$。其中 $n$ 为字符串 $s$ 的长度；而 $C$ 为字符集的大小，本题中 $C=26$。

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

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, f = 0;
    int n = s.length();
    for (int i = 0; i < n; ++i) {
      int v = d[s.charAt(i) - 'a'];
      f = Math.max(f, 0) + v;
      ans = Math.max(ans, f);
    }
    return ans;
  }
}

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, f = 0;
    for (char& c : s) {
      int v = d[c - 'a'];
      f = max(f, 0) + v;
      ans = max(ans, f);
    }
    return ans;
  }
};

func maximumCostSubstring(s string, chars string, vals []int) (ans int) {
  d := [26]int{}
  for i := range d {
    d[i] = i + 1
  }
  for i, c := range chars {
    d[c-'a'] = vals[i]
  }
  f := 0
  for _, c := range s {
    v := d[c-'a']
    f = max(f, 0) + v
    ans = max(ans, f)
  }
  return
}

function maximumCostSubstring(s: string, chars: string, vals: number[]): number {
  const d: number[] = Array.from({ length: 26 }, (_, i) => i + 1);
  for (let i = 0; i < chars.length; ++i) {
    d[chars.charCodeAt(i) - 97] = vals[i];
  }
  let ans = 0;
  let f = 0;
  for (const c of s) {
    f = Math.max(f, 0) + d[c.charCodeAt(0) - 97];
    ans = Math.max(ans, f);
  }
  return ans;
}