impl Solution {
    pub fn max_sum_after_partitioning(a: Vec<i32>, k: i32) -> i32 {
        let mut dp = vec![0; a.len() + 1];
        for i in 0..a.len() {
            let mut m = a[i];
            let mut j = 0;
            while j < k as usize && i >= j {
                m = std::cmp::max(m, a[i - j]);
                dp[i + 1] = std::cmp::max(dp[i + 1], dp[i + 1 - (j + 1)] + m * (j as i32 + 1));
                j += 1;
            }
        }

        return dp[a.len()];
    }
}

impl Solution {
    pub fn remove_duplicates(s: String) -> String {
        let mut stack = vec![];
        let mut ans = "".to_string();
        for c in s.chars() {
            if stack.is_empty() || c != *stack.get(stack.len() - 1).unwrap() {
                stack.push(c); continue;
            }
            if c == *stack.get(stack.len() - 1).unwrap() {
                stack.pop();
            }
        }
        while !stack.is_empty() {
            ans.push(stack.pop().unwrap());
        }
        return ans.chars().rev().collect::<String>();
    }
} 

use std::collections::HashMap;

impl Solution {
    pub fn longest_str_chain(words: Vec<String>) -> i32 {
        let (mut ans, mut w) = (0, words);
        w.sort_by_key(|x| x.len());
        let mut map = HashMap::new();

        for word in w {
            if map.contains_key(&word) {
                continue;
            }
            map.insert(word.clone(), 1);
            for i in 0..word.len() {
                let mut c = word.clone();
                c.remove(i);
                if map.contains_key(&c) &&
                    (*map.get(&c).unwrap() + 1 > *map.get(&word).unwrap()) {
                    map.insert(word.clone(), map.get(&c).unwrap() + 1);
                }
            }
            ans = std::cmp::max(ans, *map.get(&word).unwrap());
        }
        return ans;
    }
}