{"id":7169,"date":"2020-07-26T13:01:53","date_gmt":"2020-07-26T20:01:53","guid":{"rendered":"https:\/\/zxi.mytechroad.com\/blog\/?p=7169"},"modified":"2020-07-29T09:40:07","modified_gmt":"2020-07-29T16:40:07","slug":"leetcode-1531-string-compression-ii","status":"publish","type":"post","link":"https:\/\/zxi.mytechroad.com\/blog\/dynamic-programming\/leetcode-1531-string-compression-ii\/","title":{"rendered":"\u82b1\u82b1\u9171 LeetCode 1531. String Compression II"},"content":{"rendered":"\n<figure class=\"wp-block-embed-youtube wp-block-embed is-type-video is-provider-youtube wp-embed-aspect-16-9 wp-has-aspect-ratio\"><div class=\"wp-block-embed__wrapper\">\n<iframe loading=\"lazy\" title=\"\u82b1\u82b1\u9171 LeetCode 1531. String Compression II - \u5237\u9898\u627e\u5de5\u4f5c EP347\" width=\"500\" height=\"281\" src=\"https:\/\/www.youtube.com\/embed\/UIK00l_AiPQ?feature=oembed\" frameborder=\"0\" allow=\"accelerometer; autoplay; clipboard-write; encrypted-media; gyroscope; picture-in-picture; web-share\" referrerpolicy=\"strict-origin-when-cross-origin\" allowfullscreen><\/iframe>\n<\/div><\/figure>\n\n\n\n<p><a href=\"http:\/\/en.wikipedia.org\/wiki\/Run-length_encoding\">Run-length encoding<\/a>&nbsp;is a string compression method that works by&nbsp;replacing consecutive identical characters (repeated 2 or more times) with the concatenation of the character and the number marking the count of the characters (length of the run). For example, to compress the string&nbsp;<code>\"aabccc\"<\/code>&nbsp;we replace&nbsp;<code>\"aa\"<\/code>&nbsp;by&nbsp;<code>\"a2\"<\/code>&nbsp;and replace&nbsp;<code>\"ccc\"<\/code>&nbsp;by&nbsp;<code>\"c3\"<\/code>. Thus the compressed string becomes&nbsp;<code>\"a2bc3\"<\/code>.<\/p>\n\n\n\n<p>Notice that in this problem, we are not adding&nbsp;<code>'1'<\/code>&nbsp;after single characters.<\/p>\n\n\n\n<p>Given a&nbsp;string&nbsp;<code>s<\/code>&nbsp;and an integer&nbsp;<code>k<\/code>. You need to delete&nbsp;<strong>at most<\/strong>&nbsp;<code>k<\/code>&nbsp;characters from&nbsp;<code>s<\/code>&nbsp;such that the run-length encoded version of&nbsp;<code>s<\/code>&nbsp;has minimum length.<\/p>\n\n\n\n<p>Find the&nbsp;<em>minimum length of the run-length encoded&nbsp;version of&nbsp;<\/em><code>s<\/code><em>&nbsp;after deleting at most&nbsp;<\/em><code>k<\/code><em>&nbsp;characters<\/em>.<\/p>\n\n\n\n<p><strong>Example 1:<\/strong><\/p>\n\n\n\n<pre class=\"wp-block-preformatted;crayon:false\"><strong>Input:<\/strong> s = \"aaabcccd\", k = 2\n<strong>Output:<\/strong> 4\n<strong>Explanation: <\/strong>Compressing s without deleting anything will give us \"a3bc3d\" of length 6. Deleting any of the characters 'a' or 'c' would at most decrease the length of the compressed string to 5, for instance delete 2 'a' then we will have s = \"abcccd\" which compressed is abc3d. Therefore, the optimal way is to delete 'b' and 'd', then the compressed version of s will be \"a3c3\" of length 4.<\/pre>\n\n\n\n<p><strong>Example 2:<\/strong><\/p>\n\n\n\n<pre class=\"wp-block-preformatted;crayon:false\"><strong>Input:<\/strong> s = \"aabbaa\", k = 2\n<strong>Output:<\/strong> 2\n<strong>Explanation: <\/strong>If we delete both 'b' characters, the resulting compressed string would be \"a4\" of length 2.\n<\/pre>\n\n\n\n<p><strong>Example 3:<\/strong><\/p>\n\n\n\n<pre class=\"wp-block-preformatted;crayon:false\"><strong>Input:<\/strong> s = \"aaaaaaaaaaa\", k = 0\n<strong>Output:<\/strong> 3\n<strong>Explanation: <\/strong>Since k is zero, we cannot delete anything. The compressed string is \"a11\" of length 3.\n<\/pre>\n\n\n\n<p><strong>Constraints:<\/strong><\/p>\n\n\n\n<ul class=\"wp-block-list\"><li><code>1 &lt;= s.length &lt;= 100<\/code><\/li><li><code>0 &lt;= k &lt;= s.length<\/code><\/li><li><code>s<\/code>&nbsp;contains only lowercase English letters.<\/li><\/ul>\n\n\n\n<h2 class=\"wp-block-heading\"><strong>Solution 0: Brute Force DFS (TLE)<\/strong><\/h2>\n\n\n\n<p>Time complexity: O(C(n,k))<br>Space complexity: O(k)<\/p>\n\n\n\n<div class=\"responsive-tabs\">\n<h2 class=\"tabtitle\">C++<\/h2>\n<div class=\"tabcontent\">\n\n<pre lang=\"c++\">\nclass Solution {\npublic:\n  int getLengthOfOptimalCompression(string s, int k) {\n    const int n = s.length();\n    auto encode = [&]() -> int {\n      char p = '$';\n      int count = 0;\n      int len = 0;\n      for (char c : s) {\n        if (c == '.') continue;\n        if (c != p) {\n          p = c;\n          count = 0;\n        }\n        ++count;\n        if (count <= 2 || count == 10 || count == 100)\n          ++len;               \n      }\n      return len;\n    };\n    function<int(int, int)> dfs = [&](int start, int k) -> int {\n      if (start == n || k == 0) return encode();\n      int ans = n;\n      for (int i = start; i < n; ++i) {\n        char c = s[i];\n        s[i] = '.'; \/\/ delete\n        ans = min(ans, dfs(i + 1, k - 1));\n        s[i] = c;\n      }\n      return ans;\n    };\n    return dfs(0, k);\n  }\n};\n<\/pre>\n<\/div><\/div>\n\n\n\n<h2 class=\"wp-block-heading\"><strong>Solution1: DP<\/strong><\/h2>\n\n\n\n<figure class=\"wp-block-image size-large\"><img loading=\"lazy\" decoding=\"async\" width=\"960\" height=\"540\" src=\"https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2020\/07\/1531-ep347-2.png\" alt=\"\" class=\"wp-image-7175\" srcset=\"https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2020\/07\/1531-ep347-2.png 960w, https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2020\/07\/1531-ep347-2-300x169.png 300w, https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2020\/07\/1531-ep347-2-768x432.png 768w\" sizes=\"auto, (max-width: 960px) 100vw, 960px\" \/><\/figure>\n\n\n\n<p>State: <br>i: the start index of the substring<br>last: last char<br>len: run-length<br>k: # of chars that can be deleted.<br><br>base case:<br>1. k &lt; 0: return inf # invalid <br>2. i &gt;= s.length(): return 0 # done<br><\/p>\n\n\n\n<p>Transition:<br>1. if s[i] == last: return carry + dp(i + 1, last, len + 1, k)<\/p>\n\n\n\n<p>2. if s[i] != last:<br>  return min(1 + dp(i + 1, s[i], 1, k, #  start a new group with s[i]<br>     dp(i + 1, last, len, k -1) # delete \/ skip s[i], keep it as is.<\/p>\n\n\n\n<p>Time complexity: O(n^3*26)<br>Space complexity: O(n^3*26) <\/p>\n\n\n\n<div class=\"responsive-tabs\">\n<h2 class=\"tabtitle\">C++<\/h2>\n<div class=\"tabcontent\">\n\n<pre lang=\"c++\">\nint cache[101][27][101][101];\nclass Solution {\npublic:\n  int getLengthOfOptimalCompression(string s, int k) {    \n    memset(cache, -1, sizeof(cache));\n    \/\/ Min length of compressioned string of s[i:]    \n    \/\/ 1. last char is |last|\n    \/\/ 2. current run-length is len\n    \/\/ 3. we can delete k chars.\n    function<int(int, int, int, int)> dp = \n      [&](int i, int last, int len, int k) {\n      if (k < 0) return INT_MAX \/ 2;\n      if (i >= s.length()) return 0;      \n      int& ans = cache[i][last][len][k];\n      if (ans != -1) return ans;\n      if (s[i] - 'a' == last) { \n        \/\/ same as the previous char, no need to delete.\n        int carry = (len == 1 || len == 9 || len == 99);\n        ans = carry + dp(i + 1, last, len + 1, k);\n      } else {\n        ans = min(1 + dp(i + 1, s[i] - 'a', 1, k),  \/\/ keep s[i]\n                      dp(i + 1, last, len, k - 1)); \/\/ delete s[i]\n      }\n      return ans;\n    };\n    return dp(0, 26, 0, k);\n  }\n};\n<\/pre>\n<\/div><\/div>\n\n\n\n<h2 class=\"wp-block-heading\"><strong>State compression<\/strong><\/h2>\n\n\n\n<figure class=\"wp-block-image size-large\"><img loading=\"lazy\" decoding=\"async\" width=\"960\" height=\"540\" src=\"https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2020\/07\/1531-ep347-3.png\" alt=\"\" class=\"wp-image-7174\" srcset=\"https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2020\/07\/1531-ep347-3.png 960w, https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2020\/07\/1531-ep347-3-300x169.png 300w, https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2020\/07\/1531-ep347-3-768x432.png 768w\" sizes=\"auto, (max-width: 960px) 100vw, 960px\" \/><\/figure>\n\n\n\n<p>dp[i][k] := min len of s[i:] encoded by deleting at most k charchters.<\/p>\n\n\n\n<p>dp[i][k] = min(dp[i+1][k-1] # delete s[i]<br>encode_len(s[i~j] == s[i]) + dp(j+1, k - sum(s[i~j])) for j in range(i, n)) # keep<\/p>\n\n\n\n<p>Time complexity: O(n^2*k)<br>Space complexity: O(n*k)<\/p>\n\n\n\n<div class=\"responsive-tabs\">\n<h2 class=\"tabtitle\">C++<\/h2>\n<div class=\"tabcontent\">\n\n<pre lang=\"c++\">\n\/\/ Author: Huahua\nclass Solution {\npublic:\n  int getLengthOfOptimalCompression(string s, int k) {    \n    const int n = s.length();\n    vector<vector<int>> cache(n, vector<int>(k + 1, -1));\n    function<int(int, int)> dp = [&](int i, int k) -> int {\n      if (k < 0) return n;\n      if (i + k >= n) return 0;\n      int& ans = cache[i][k];\n      if (ans != -1) return ans;\n      ans = dp(i + 1, k - 1); \/\/ delete      \n      int len = 0;\n      int same = 0;\n      int diff = 0;\n      for (int j = i; j < n &#038;&#038; diff <= k; ++j) {\n        if (s[j] == s[i] &#038;&#038; ++same) {\n          if (same <= 2 || same == 10 || same == 100) ++len;\n        } else {\n          ++diff;\n        }\n        ans = min(ans, len + dp(j + 1, k - diff));\n      }\n      return ans;\n    };\n    return dp(0, k);\n  }\n};\n<\/pre>\n\n<\/div><h2 class=\"tabtitle\">Java<\/h2>\n<div class=\"tabcontent\">\n\n<pre>\n\/\/ Author: Huahua\nclass Solution {\n  private int[][] dp;\n  private char[] s;\n  private int n;\n  \n  public int getLengthOfOptimalCompression(\n    String s, int k) {\n    this.s = s.toCharArray();\n    this.n = s.length();\n    this.dp = new int[n][k + 1];\n    for (int[] row : dp)\n      Arrays.fill(row, -1);\n    return dp(0, k);\n  }  \n  \n  private int dp(int i, int k) {\n    if (k < 0) return this.n;\n    if (i + k >= n) return 0; \/\/ done or delete all.    \n    int ans = dp[i][k];\n    if (ans != -1) return ans;\n    ans = dp(i + 1, k - 1); \/\/ delete s[i]\n    int len = 0;\n    int same = 0;    \n    int diff = 0;\n    for (int j = i; j < n &#038;&#038; diff <= k; ++j) {\n      if (s[j] == s[i]) {\n        ++same;\n        if (same <= 2 || same == 10 || same == 100) ++len;\n      } else {\n        ++diff;\n      }      \n      ans = Math.min(ans, len + dp(j + 1, k - diff)); \n    }\n    dp[i][k] = ans;\n    return ans;\n  }\n}\n<\/pre>\n\n<\/div><h2 class=\"tabtitle\">Python3<\/h2>\n<div class=\"tabcontent\">\n\n<pre lang=\"python\">\n# Author: Huahua\nclass Solution:\n  def getLengthOfOptimalCompression(self, s: str, k: int) -> int:\n    n = len(s)\n    @functools.lru_cache(maxsize=None)\n    def dp(i, k):\n      if k < 0: return n\n      if i + k >= n: return 0\n      ans = dp(i + 1, k - 1)\n      l = 0\n      same = 0\n      for j in range(i, n):\n        if s[j] == s[i]:\n          same += 1\n          if same <= 2 or same == 10 or same == 100:\n            l += 1\n        diff = j - i + 1 - same\n        if diff < 0: break\n        ans = min(ans, l + dp(j + 1, k - diff))\n      return ans\n    return dp(0, k)\n<\/pre>\n<\/div><\/div>\n","protected":false},"excerpt":{"rendered":"<p>Run-length encoding&nbsp;is a string compression method that works by&nbsp;replacing consecutive identical characters (repeated 2 or more times) with the concatenation of the character and the&#8230;<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[46],"tags":[18,272,217,431,271],"class_list":["post-7169","post","type-post","status-publish","format-standard","hentry","category-dynamic-programming","tag-dp","tag-encoding","tag-hard","tag-optimization","tag-run-length","entry","simple"],"_links":{"self":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/7169","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/comments?post=7169"}],"version-history":[{"count":5,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/7169\/revisions"}],"predecessor-version":[{"id":7179,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/7169\/revisions\/7179"}],"wp:attachment":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/media?parent=7169"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/categories?post=7169"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/tags?post=7169"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}