LeetCode2272

发表于 分类于 ， 本文字数： 1.5k 阅读时长 ≈ 5 分钟

LeetCode.2272:最大波动的子字符串

​ 3.16凌晨做的，没做明白。本科的时候上动态规划的时候不该逃课的，对不起你sz老师。

题目描述

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

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

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

示例

示例1：

1
2
3
4
5
6
7
8
9
输入：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：

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

提示：

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

官方题解：枚举最多和最少的字符 + 最大子段 和 动态规划

全局思路

​ 如果我们枚举给定字符串 s 的所有子串并计算波动值，那么至少需要$ O(n^2 )$ 的时间，其中 n 是字符串 s 的长度。这是因为 s 的子串有 $O(n^2)$ 个，然而本题 $n≤10^4$ ，会TLE。

​ 因此我们可以考虑枚举「出现次数最多的字符」以及「出现次数最少的字符」。即将s中所有字符对进行枚举，如果出现次数最多的字符为 $c_0$ ，最少的字符为 $c_1$ ，并且我们可以将字符串 s 映射成一个数组：

  • 如果某个字符为 $c_0$ ，那么映射为 +1;

  • 如果某个字符为 $c_1$ ，那么映射为 −1；

  • 对于其余情况，映射为 0。

​ 那么任意一个子串对应的子数组的和，就是$「c_0 出现的次数减去 c_1 出现的次数」$。我们只要求出映射数组的$「最大子段和」$（就是和最大的子数组的和），就可以知道在以 $c_0$ 为出现次数最多的字符、$c_1$ 为出现次数最少的字符时，最大的波动值。

对于某个子串，如果 $c_0$ 并非真正出现次数最多的字符，或者 $c_1$ 并非出现次数最少的字符，我们在计算答案时也不会产生影响。例如 $c_0′$ 是真正出现次数最多的字符，我们计算出的最大波动值为$「c_0 出现的次数减去 c_1 出现的次数」$，而真正的答案$「c_0′ 出现的次数减去 c_1 出现的次数」$只会更大，并且会在枚举$ (c_0′ ,c1 )$ 时计算出来。

动态规划

当给定一个只包含 +1,0,−1 的数组，如何计算最大子段和呢？需要注意的是，满足要求的子数组必须至少包含一个 +1 和一个 −1，否则我们会将例如只包含$ c_0$ 而不包含$ c_1$ 的子串计入答案。由于不包含 +1 的子数组一定不是答案（此时子数组的和为负数，而答案一定是非负整数），因此在进行动态规划时，我们只需要一个额外的状态，即$「包含 −1 的子数组」$。

我们用 $f[i]$ 表示以 i 结尾的子数组的最大和，$g[i]$ 表示以 i 结尾的并且一定包含 −1 的子数组的最大和。初始时 $f[−1]=0$ 以及$ g[−1]=−∞$，因为 f 的定义可以允许一个空的子数组，而 g 不可以（因为一定要包含 −1）。记 $d_i$ 表示$ s[i] $映射的数值，当$ d_i =0 $时，状态转移方程为：

  • $f[i] = f[i−1]$
  • $g[i]=g[i−1]$

当 $d_i =1$ 时，状态转移方程为：

  • $f[i]=max(f[i−1],0)+1$
  • $g[i]=g[i−1]+1$

当 $d_i =−1$ 时，状态转移方程为：

  • $f[i]=max(f[i−1],0)−1$
  • $g[i]=max(f[i−1],g[i−1],0)−1$

最终的答案为数组 g 中的最大值。

优化

上述算法的时间复杂度为$ O(n\lvert\sum\rvert^2 )$，其中 $\sum$ 表示字符集。但注意到当 $d_i =0$ 时，我们实际上没有进行任何计算，因此我们可以对动态规划的时间进行优化。

我们使用哈希映射递增地存储每一个字符出现的位置。当枚举到 $(c_0 ,c_1 ) $时，我们使用类似$「合并两个有序列表」$的方法进行动态规划，这样就可以完成所有$ d_i =±1 $的计算，并且跳过了$ d_i =0$ 的位置。具体实现可以参考题解代码。

由于每种字符会被枚举到 $2\lvert\sum\rvert−1$ 次，而所有字符的出现次数总和为 n，因此优化后的算法的时间复杂度为 $O((2\lvert\sum\rvert−1)n)−O(\lvert\sum\rvert)$。

题解代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
class Solution {
public:
    int largestVariance(string s) {
        unordered_map<char, vector<int>> pos;
        for (int i = 0; i < s.size(); ++i) {
            pos[s[i]].push_back(i);
        }

        int ans = 0;
        for (auto&& [c0, pos0]: pos) {
            for (auto&& [c1, pos1]: pos) {
                if (c0 != c1) {
                    int i = 0, j = 0;
                    int f = 0, g = INT_MIN;
                    while (i < pos0.size() || j < pos1.size()) {
                        if (j == pos1.size() || (i < pos0.size() && pos0[i] < pos1[j])) {
                            tie(f, g) = tuple{max(f, 0) + 1, g + 1};
                            ++i;
                        }
                        else {
                            tie(f, g) = tuple{max(f, 0) - 1, max({f, g, 0}) - 1};
                            ++j;
                        }
                        ans = max(ans, g);
                    }
                }
            }
        }
        return ans;
    }
};

复杂度分析：

时间复杂度：$O(n\lvert\sum\rvert)$，其中 n 是字符串 s 的长度，$\sum$ 是字符集，在本题中 $\lvert\sum\rvert = 26$。

空间复杂度：$O(n)$，即为哈希映射需要使用的空间。