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

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

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

注意：必须同时有，最多字符和最少字符的字符串才是有效的。

输入：s = "aababbb"。

输出：3。

答案2022-09-01：

方法一：自然智慧，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;}

执行结果如下：

***

[左神java代码]()