返回介绍

solution / 2200-2299 / 2272.Substring With Largest Variance / README

发布于 2024-06-17 01:03:08 字数 4045 浏览 0 评论 0 收藏 0

2272. 最大波动的子字符串

English Version

题目描述

字符串的 波动 定义为子字符串中出现次数 最多 的字符次数与出现次数 最少 的字符次数之差。

给你一个字符串 s ,它只包含小写英文字母。请你返回 s 里所有 子字符串的 最大波动 值。

子字符串 是一个字符串的一段连续字符序列。

 

示例 1:

输入:s = "aababbb"
输出:3
解释:
所有可能的波动值和它们对应的子字符串如以下所示:
- 波动值为 0 的子字符串:"a" ,"aa" ,"ab" ,"abab" ,"aababb" ,"ba" ,"b" ,"bb" 和 "bbb" 。
- 波动值为 1 的子字符串:"aab" ,"aba" ,"abb" ,"aabab" ,"ababb" ,"aababbb" 和 "bab" 。
- 波动值为 2 的子字符串:"aaba" ,"ababbb" ,"abbb" 和 "babb" 。
- 波动值为 3 的子字符串 "babbb" 。
所以,最大可能波动值为 3 。

示例 2:

输入:s = "abcde"
输出:0
解释:
s 中没有字母出现超过 1 次,所以 s 中每个子字符串的波动值都是 0 。

 

提示:

  • 1 <= s.length <= 104
  • s  只包含小写英文字母。

解法

方法一:枚举 + 动态规划

由于字符集只包含小写字母,我们可以考虑枚举出现次数最多的字符 $a$ 以及出现次数最少的字符 $b$。对于一个子串来说,这两种字符出现的次数之差就是子串的波动值。

具体实现上,我们使用双重循环枚举 $a$ 和 $b$,用 $f[0]$ 记录以当前字符结尾的连续出现字符 $a$ 的个数,用 $f[1]$ 记录以当前字符结尾的,并且包含 $a$ 和 $b$ 的子串的波动值。迭代取 $f[1]$ 的最大值即可。

递推公式如下:

  1. 如果当前字符为 $a$,则 $f[0]$ 和 $f[1]$ 都加 $1$;
  2. 如果当前字符为 $b$,则 $f[1]=\max(f[1]-1, f[0]-1)$,而 $f[0]=0$;
  3. 否则,无需考虑。

注意,初始时将 $f[1]$ 赋值为一个负数最大值,可以保证更新答案时是合法的。

时间复杂度 $O(n\times C^2)$,其中 $n$ 表示字符串 $s$ 的长度,而 $C$ 为字符集大小,本题中 $C=26$。

class Solution:
  def largestVariance(self, s: str) -> int:
    ans = 0
    for a, b in permutations(ascii_lowercase, 2):
      if a == b:
        continue
      f = [0, -inf]
      for c in s:
        if c == a:
          f[0], f[1] = f[0] + 1, f[1] + 1
        elif c == b:
          f[1] = max(f[1] - 1, f[0] - 1)
          f[0] = 0
        if ans < f[1]:
          ans = f[1]
    return ans
class Solution {
  public int largestVariance(String s) {
    int n = s.length();
    int ans = 0;
    for (char a = 'a'; a <= 'z'; ++a) {
      for (char b = 'a'; b <= 'z'; ++b) {
        if (a == b) {
          continue;
        }
        int[] f = new int[] {0, -n};
        for (int i = 0; i < n; ++i) {
          if (s.charAt(i) == a) {
            f[0]++;
            f[1]++;
          } else if (s.charAt(i) == b) {
            f[1] = Math.max(f[0] - 1, f[1] - 1);
            f[0] = 0;
          }
          ans = Math.max(ans, f[1]);
        }
      }
    }
    return ans;
  }
}
class Solution {
public:
  int largestVariance(string s) {
    int n = s.size();
    int ans = 0;
    for (char a = 'a'; a <= 'z'; ++a) {
      for (char b = 'a'; b <= 'z'; ++b) {
        if (a == b) continue;
        int f[2] = {0, -n};
        for (char c : s) {
          if (c == a) {
            f[0]++;
            f[1]++;
          } else if (c == b) {
            f[1] = max(f[1] - 1, f[0] - 1);
            f[0] = 0;
          }
          ans = max(ans, f[1]);
        }
      }
    }
    return ans;
  }
};
func largestVariance(s string) int {
  ans, n := 0, len(s)
  for a := 'a'; a <= 'z'; a++ {
    for b := 'a'; b <= 'z'; b++ {
      if a == b {
        continue
      }
      f := [2]int{0, -n}
      for _, c := range s {
        if c == a {
          f[0]++
          f[1]++
        } else if c == b {
          f[1] = max(f[1]-1, f[0]-1)
          f[0] = 0
        }
        ans = max(ans, f[1])
      }
    }
  }
  return ans
}

如果你对这篇内容有疑问,欢迎到本站社区发帖提问 参与讨论,获取更多帮助,或者扫码二维码加入 Web 技术交流群。

扫码二维码加入Web技术交流群

发布评论

需要 登录 才能够评论, 你可以免费 注册 一个本站的账号。
列表为空,暂无数据
    我们使用 Cookies 和其他技术来定制您的体验包括您的登录状态等。通过阅读我们的 隐私政策 了解更多相关信息。 单击 接受 或继续使用网站,即表示您同意使用 Cookies 和您的相关数据。
    原文