aboutsummaryrefslogtreecommitdiff
path: root/string_compression2.c
blob: 206af5e8b178cb630a60d0d8026b16d6319284d6 (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
// 1531. String Compression II
#include "leetcode.h"

/*
 * run-length encoding is a string compression method that works by replacing
 * consecutive identical characters (repeated 2 or more times) with the
 * concatenation of the characters and the number marking the count of the
 * characters (length of run). for example tocompress the string "aabccc", we
 * replace "aa" by "a2" and replace "ccc" by "c3". thus the compressed string
 * becomes "a2bc3". notice that in this problem we are not adding '1' after
 * single characters. given a string 's' and an integer 'k'. you needed to
 * delete at most 'k' characters from 's' such that the run-length encoded
 * version of 's' has minimum length. find the minimum length of the run-length
 * encoded version of 's' after deleting at most 'k' characters
 */

int dp[101][101];
int dfs(char *s, int left, int k) {
  int j = k;
  if (strlen(s) - left <= j)
    return 0;
  if (dp[left][j] >= 0)
    return dp[left][j];
  int res = j ? dfs(s, left + 1, k - 1) : 100, c = 1;
  for (int i = left + 1; i <= strlen(s); ++i) {
    res = fmin(res, dfs(s, i, j) + 1 +
                        (c >= 100 ? 3 : (c >= 10 ? 2 : (c > 1 ? 1 : 0))));
    if (i == strlen(s))
      break;
    if (s[i] == s[left])
      ++c;
    else if (--k < 0)
      break;
  }
  return dp[left][k] = res;
}

int getLengthOfOptimalCompression(char *s, int k) {
  memset(dp, -1, sizeof(dp));
  return dfs(s, 0, k);
}

int main() {
  char *s1 = "aaabcccd", *s2 = "aabbaa", *s3 = "aaaaaaaaaaa";
  printf("%d\n", getLengthOfOptimalCompression(s1, 2)); // expect: 4
  printf("%d\n", getLengthOfOptimalCompression(s2, 2)); // expect: 2
  printf("%d\n", getLengthOfOptimalCompression(s3, 0)); // expect: 0
}