class Solution {
public:
int largestVariance(string s) {
}
};
2272. 最大波动的子字符串
字符串的 波动 定义为子字符串中出现次数 最多 的字符次数与出现次数 最少 的字符次数之差。
给你一个字符串 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 <= 104s 只包含小写英文字母。原站题解
cpp 解法, 执行用时: 24 ms, 内存消耗: 6.5 MB, 提交时间: 2023-09-06 23:58:48
class Solution {
public:
// 优化版
int largestVariance(string &s) {
int ans = 0;
int diff[26][26] = {}, diff_with_b[26][26];
memset(diff_with_b, 0x80, sizeof(diff_with_b));
for (char ch : s) {
ch -= 'a';
for (char i = 0; i < 26; ++i) {
if (i == ch) continue;
++diff[ch][i]; // a=ch, b=i
++diff_with_b[ch][i];
diff_with_b[i][ch] = --diff[i][ch]; // a=i, b=ch
diff[i][ch] = max(diff[i][ch], 0);
ans = max(ans, max(diff_with_b[ch][i], diff_with_b[i][ch]));
}
}
return ans;
}
/*
int largestVariance(string &s) {
int ans = 0;
for (char a = 'a'; a <= 'z'; ++a)
for (char b = 'a'; b <= 'z'; ++b) {
if (a == b) continue;
int diff = 0, diff_with_b = -s.length();
for (char ch : s) {
if (ch == a) {
++diff;
++diff_with_b;
} else if (ch == b) {
diff_with_b = --diff;
diff = max(diff, 0);
}
ans = max(ans, diff_with_b);
}
}
return ans;
}
*/
};
java 解法, 执行用时: 14 ms, 内存消耗: 40.7 MB, 提交时间: 2023-09-06 23:57:33
class Solution {
/*
public int largestVariance(String s) {
var ans = 0;
for (var a = 'a'; a <= 'z'; ++a)
for (var b = 'a'; b <= 'z'; ++b) {
if (a == b) continue;
var diff = 0;
var diffWithB = -s.length();
for (var i = 0; i < s.length(); i++) {
if (s.charAt(i) == a) {
++diff;
++diffWithB;
} else if (s.charAt(i) == b) {
diffWithB = --diff;
diff = Math.max(diff, 0);
}
ans = Math.max(ans, diffWithB);
}
}
return ans;
}
*/
// 优化版
public int largestVariance(String s) {
var ans = 0;
var diff = new int[26][26];
var diffWithB = new int[26][26];
for (var i = 0; i < 26; i++) Arrays.fill(diffWithB[i], -s.length());
for (var k = 0; k < s.length(); k++) {
var ch = s.charAt(k) - 'a';
for (var i = 0; i < 26; ++i) {
if (i == ch) continue;
++diff[ch][i]; // a=ch, b=i
++diffWithB[ch][i];
diffWithB[i][ch] = --diff[i][ch]; // a=i, b=ch
diff[i][ch] = Math.max(diff[i][ch], 0);
ans = Math.max(ans, Math.max(diffWithB[ch][i], diffWithB[i][ch]));
}
}
return ans;
}
}
golang 解法, 执行用时: 8 ms, 内存消耗: 2.2 MB, 提交时间: 2023-09-06 23:56:38
func largestVariance(s string) (ans int) {
var diff, diffWithB [26][26]int
for i := 0; i < 26; i++ {
for j := 0; j < 26; j++ {
diffWithB[i][j] = -len(s)
}
}
for _, ch := range s {
ch -= 'a'
for i := rune(0); i < 26; i++ {
if i == ch {
continue
}
diff[ch][i]++ // a=ch, b=i
diffWithB[ch][i]++
diff[i][ch]-- // a=i, b=ch
diffWithB[i][ch] = diff[i][ch]
diff[i][ch] = max(diff[i][ch], 0)
ans = max(ans, max(diffWithB[ch][i], diffWithB[i][ch]))
}
}
return
}
/*
func largestVariance(s string) (ans int) {
for a := 'a'; a <= 'z'; a++ {
for b := 'a'; b <= 'z'; b++ {
if b == a {
continue
}
diff, diffWithB := 0, -len(s)
for _, ch := range s {
if ch == a {
diff++
diffWithB++
} else if ch == b {
diff--
diffWithB = diff // 记录包含 b 时的 diff
diff = max(diff, 0)
}
ans = max(ans, diffWithB)
}
}
}
return
}
*/
func max(a, b int) int { if b > a { return b }; return a }
python3 解法, 执行用时: 824 ms, 内存消耗: 16.2 MB, 提交时间: 2023-09-06 23:55:28
class Solution:
'''
def largestVariance(self, s: str) -> int:
ans = 0
for a, b in permutations(ascii_lowercase, 2):
diff, diff_with_b = 0, -inf
for ch in s:
if ch == a:
diff += 1
diff_with_b += 1
elif ch == b:
diff -= 1
diff_with_b = diff # 记录包含 b 时的 diff
if diff < 0:
diff = 0
if diff_with_b > ans:
ans = diff_with_b
return ans
'''
# 在遍历 s 的过程中将 s[i] 作为 a 或 b，减少枚举次数，从而优化时间复杂度
def largestVariance(self, s: str) -> int:
if s.count(s[0]) == len(s):
return 0
ans = 0
diff = [[0] * 26 for _ in range(26)]
diff_with_b = [[-inf] * 26 for _ in range(26)]
for ch in s:
ch = ord(ch) - ord('a')
for i in range(26):
if i == ch:
continue
diff[ch][i] += 1 # a=ch, b=i
diff_with_b[ch][i] += 1
diff[i][ch] -= 1 # a=i, b=ch
diff_with_b[i][ch] = diff[i][ch]
if diff[i][ch] < 0:
diff[i][ch] = 0
ans = max(ans, diff_with_b[ch][i], diff_with_b[i][ch])
return ans