aboutsummaryrefslogtreecommitdiff
path: root/string_compression2.rs
blob: 792a0ac7c74a56d13ec8952b64a142e667bd1c6f (plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
struct Solution;

impl Solution {
    pub fn get_length_of_optimal_compression(s: String, k: i32) -> i32 {
        #[inline]
        fn len_of_chars(n: i32) -> i32 {
            match n {
                1 => 1,
                2..=9 => 2,
                10..=99 => 3,
                _ => 4,
            }
        }
        fn dfs(v: &[u8], dp: &mut [[i32; 101]; 101], left: i32, k_s: i32) -> i32 {
            let mut k = k_s;
            if v.len() as i32 - left <= k {
                return 0;
            }
            if dp[left as usize][k as usize] >= 0 {
                return dp[left as usize][k as usize];
            }
            let mut ans = if k > 0 {
                dfs(v, dp, left + 1, k - 1)
            } else {
                std::i32::MAX
            };
            let mut c = 1;
            for i in left + 1..=v.len() as i32 {
                ans = ans.min(dfs(v, dp, i, k) + len_of_chars(c));
                if i == v.len() as i32 {
                    break;
                }
                if v[i as usize] == v[left as usize] {
                    c += 1;
                } else {
                    k -= 1;
                    if k < 0 {
                        break;
                    }
                }
            }
            dp[left as usize][k_s as usize] = ans;
            ans
        }
        let mut dp = [[-1; 101]; 101];
        let v = s.as_bytes();
        dfs(v, &mut dp, 0, k)
    }
}

fn main() {
    let s = String::from("aaabcccd");
    print!("{}", Solution::get_length_of_optimal_compression(s, 2));
}