字符串的 波动 定义为子字符串中出现次数 最多 的字符次数与出现次数 最少 的字符次数之差。
给你一个字符串 s ，它只包含小写英文字母。请你返回 s 里所有 子字符串的 最大波动 值。
子字符串 是一个字符串的一段连续字符序列。
注意：必须同时有，最多字符和最少字符的字符串才是有效的。
输入：s = “aababbb”。
输出：3。
方法一：自然智慧，3个for循环。
方法二：动态规划。
代码用rust编写。代码如下：
fn main() {
let s = "aababbb";
let ans = largest_variance1(s);
println!("ans = {}", ans);
let ans = largest_variance2(s);
println!("ans = {}", ans);
}
fn largest_variance1(s: &str) -> i32 {
if s.len() == 0 {
return 0;
}
let n = s.len() as i32;
// a b a c b b a
// 0 1 0 2 1 1 0
let mut arr: Vec<i32> = vec![];
for _ in 0..n {
arr.push(0);
}
let sbytes=s.as_bytes();
for i in 0..n {
arr[i as usize] = (sbytes[i as usize] - 'a' as u8) as i32;
}
let mut ans = 0;
// 26 * 26 * n O(N)
for more in 0..26 {
for less in 0..26 {
if more != less {
let mut continuous_a = 0;
let mut appear_b = false;
let mut max = 0;
// 从左到右遍历，
for i in 0..n {
if arr[i as usize] != more && arr[i as usize] != less {
continue;
}
if arr[i as usize] == more {
// 当前字符是more
continuous_a += 1;
if appear_b {
max += 1;
}
} else {
// 当前字符是B
max = get_max(max, continuous_a) - 1;
continuous_a = 0;
appear_b = true;
}
ans = get_max(ans, max);
}
}
}
}
return ans;
}
fn get_max<T: Clone + Copy + std::cmp::PartialOrd>(a: T, b: T) -> T {
if a > b {
a
} else {
b
}
}
fn largest_variance2(s: &str) -> i32 {
if s.len() == 0 {
return 0;
}
let n = s.len() as i32;
// a b a c b b a
// 0 1 0 2 1 1 0
let mut arr: Vec<i32> = vec![];
for _ in 0..n {
arr.push(0);
}
for i in 0..n {
arr[i as usize] = (s.as_bytes()[i as usize] - 'a' as u8) as i32;
}
// dp[a][b] = more a less b max
// dp[b][a] = more b less a max
let mut dp: Vec<Vec<i32>> = vec![];
// continuous[a][b] more a less b 连续出现a的次数
// continuous[b][a] more b less a 连续出现b的次数
let mut continuous: Vec<Vec<i32>> = vec![];
// appear[a][b] more a less b b有没有出现过
// appear[b][a] more b less a a有没有出现过
let mut appear: Vec<Vec<bool>> = vec![];
for i in 0..26 {
dp.push(vec![]);
continuous.push(vec![]);
appear.push(vec![]);
for _ in 0..26 {
dp[i].push(0);
continuous[i].push(0);
appear[i].push(false);
}
}
let mut ans = 0;
// 26 * N
for i in arr.iter() {
let i = *i;
for j in 0..26 {
if j != i {
// i,j
// more i less j 三个变量 连续出现i，j有没有出现过，i-j max
// more j less i 三个变量 连续出现j，i有没有出现过，j-i max
continuous[i as usize][j as usize] += 1;
if appear[i as usize][j as usize] {
dp[i as usize][j as usize] += 1;
}
if !appear[j as usize][i as usize] {
appear[j as usize][i as usize] = true;
dp[j as usize][i as usize] = continuous[j as usize][i as usize] - 1;
} else {
dp[j as usize][i as usize] = get_max(
dp[j as usize][i as usize],
continuous[j as usize][i as usize],
) - 1;
}
continuous[j as usize][i as usize] = 0;
ans = get_max(
ans,
get_max(dp[j as usize][i as usize], dp[i as usize][j as usize]),
);
}
}
}
return ans;
}执行结果如下：
