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

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代码

本作品采用《CC 协议》，转载必须注明作者和本文链接