aboutsummaryrefslogtreecommitdiff
path: root/string_compression2.rs
diff options
context:
space:
mode:
Diffstat (limited to 'string_compression2.rs')
-rw-r--r--string_compression2.rs54
1 files changed, 54 insertions, 0 deletions
diff --git a/string_compression2.rs b/string_compression2.rs
new file mode 100644
index 0000000..792a0ac
--- /dev/null
+++ b/string_compression2.rs
@@ -0,0 +1,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));
+}