[LeetCode] 2272. Substring With Largest Variance

The variance of a string is defined as the largest difference between the number of occurrences of any 2 characters present in the string. Note the two characters may or may not be the same.

Given a string s consisting of lowercase English letters only, return the largest variance possible among all substrings of s.

A substring is a contiguous sequence of characters within a string.

Example 1:

Input: s = "aababbb"
Output: 3
Explanation:
All possible variances along with their respective substrings are listed below:
- Variance 0 for substrings "a", "aa", "ab", "abab", "aababb", "ba", "b", "bb", and "bbb".
- Variance 1 for substrings "aab", "aba", "abb", "aabab", "ababb", "aababbb", and "bab".
- Variance 2 for substrings "aaba", "ababbb", "abbb", and "babb".
- Variance 3 for substring "babbb".
Since the largest possible variance is 3, we return it.

Example 2:

Input: s = "abcde"
Output: 0
Explanation:
No letter occurs more than once in s, so the variance of every substring is 0.

Constraints:

• 1 <= s.length <= 104
• s consists of lowercase English letters.

最大波动的子字符串。

字符串的 波动 定义为子字符串中出现次数 最多 的字符次数与出现次数 最少 的字符次数之差。
给你一个字符串 s ，它只包含小写英文字母。请你返回 s 里所有 子字符串的 最大波动 值。
子字符串 是一个字符串的一段连续字符序列。
来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/substring-with-largest-variance
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

思路是动态规划。这道题我参考了这个帖子，写的很详细。

做这道题之前，可以先做一下53题，思路类似，还是涉及 Kadane’s Algorithm 的一道题。53题让我们找的是和最大的子数组，当时我们的思路是定义 dp[i] 为以 nums[i] 为结尾的子数组的和，看看哪个位置上的 dp 值最大。这道题的做法类似但是很不好想，这里因为只涉及 26 个字母，所以我们可以通过枚举的方式，每两个字母凑成一对去找他们之间能形成的最大波动的子串长度。

设出现次数最多的字母为 a，视为 1，出现最少的字母为 b，视为 -1，把其余字母视为 0。这里我们需要几个变量，diff 维护 a 和 b 的出现次数之差，diffWithB 维护包含了 b 的 a 和 b 的出现次数之差，初始化为 -s.length()，因为还没有出现 b。

开始遍历字符串的时候，

• 遇到 a，diff++, diffWithB++
• 遇到 b, diff–, diffWithB = diff。如果 diff < 0，则把 diff 置为 0。因为如果当前这一段子串导致 diff 为负，留着也没用，丢弃即可。

统计所有 diffWithB 的最大值，即为答案。若 s 只有一种字符则答案为 0。

时间O(26 * 25) = O(1)

空间O(1)

Java实现

 1 class Solution {
 2     public int largestVariance(String s) {
 3         var res = 0;
 4         for (var a = 'a'; a <= 'z'; a++) {
 5             for (var b = 'a'; b <= 'z'; b++) {
 6                 if (a == b) {
 7                     continue;
 8                 }
 9                 var diff = 0;
10                 var diffWithB = -s.length();
11                 for (var i = 0; i < s.length(); i++) {
12                     if (s.charAt(i) == a) {
13                         diff++;
14                         diffWithB++;
15                     } else if (s.charAt(i) == b) {
16                         diff--;
17                         diffWithB = diff;
18                         diff = Math.max(0, diff);
19                     }
20                     res = Math.max(res, diffWithB);
21                 }
22             }
23         }
24         return res;
25     }
26 }

相关题目

53. Maximum Subarray

2272. Substring With Largest Variance

LeetCode 题目总结