Today I have done leetcode's October LeetCoding Challenge with cpp.

October LeetCoding Challenge 15

Description

String Compression II

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 character and the number marking the count of the characters (length of the run). For example, to compress 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 need 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.

Example 1:

Input: s = "aaabcccd", k = 2
Output: 4
Explanation: 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.

Example 2:

Input: s = "aabbaa", k = 2
Output: 2
Explanation: If we delete both 'b' characters, the resulting compressed string would be "a4" of length 2.

Example 3:

Input: s = "aaaaaaaaaaa", k = 0
Output: 3
Explanation: Since k is zero, we cannot delete anything. The compressed string is "a11" of length 3.

Constraints:

• 1 <= s.length <= 100
• 0 <= k <= s.length
• s contains only lowercase English letters.

Solution

A straightforward top-down dp solution's state contains position, last character, how many the last character consecutive and how many character we can delete.

class Solution {
  uint8_t memo[101][27][101][104] = {};
  string s;
  uint8_t solve(
    uint8_t pos,
    uint8_t last,
    uint8_t last_length,
    uint8_t to_delete
  ) {
    if(memo[pos][last][last_length][to_delete] != 255) {
      
      return memo[pos][last][last_length][to_delete];
    }
    if(pos + to_delete >= s.length()) {
      uint8_t add = !last_length ? 0 :
                    last_length == 1 ? 1 :
                    last_length < 10 ? 2 :
                    last_length < 100 ? 3 : 4;
      return memo[pos][last][last_length][to_delete] = add;
    }
    uint8_t result = 255;
    if(to_delete) {
      result = solve(pos + 1, last, last_length, to_delete - 1);
    }
    if(s[pos] - 'a' == last) {
      result = min(result, solve(pos + 1, last, last_length + 1, to_delete));
    } else {
      uint8_t add = !last_length ? 0 :
                    last_length == 1 ? 1 :
                    last_length < 10 ? 2 :
                    last_length < 100 ? 3 : 4;
      result = min<uint8_t>(result, add + solve(pos + 1, s[pos] - 'a', 1, to_delete));
    }
    return memo[pos][last][last_length][to_delete] = result;
  }
public:
  int getLengthOfOptimalCompression(string s, int k) {
    this->s = s;
    memset(memo, -1, sizeof(memo[0]) * (s.length() + 1));
    return solve(0, 26, 0, k);
  }
};

// Accepted
// 136/136 cases passed (517 ms)
// Your runtime beats 37.12 % of cpp submissions
// Your memory usage beats 29.54 % of cpp submissions (37.7 MB)

but the states with the same to_delete has the same result, it's because of last character distinguish these states, so we can found a way remove both last and last_length.

class Solution {
  uint8_t memo[104][104];
  string s;
  uint8_t solve(uint8_t pos, uint8_t to_delete) {
    if(memo[pos][to_delete] != 255) {
      return memo[pos][to_delete];
    }
    if(pos + to_delete >= s.length()) {
      return memo[pos][to_delete] = 0;
    }
    uint8_t result = 255;
    uint8_t origin_to_delete = to_delete;
    if(to_delete) {
      result = solve(pos + 1, to_delete - 1);
    }
    uint8_t count = 1;
    for(int i = pos + 1; i <= s.length(); ++i) {
      uint8_t add = count == 100 ? 4 :
                    count >  9   ? 3 :
                    count >  1   ? 2 :
                    1;
      result = min<uint8_t>(result, solve(i, to_delete) + add);
      if(i == s.size()) break;
      if(s[i] != s[pos] && !to_delete) break;
      if(s[i] == s[pos]) {
        count += 1;
      } else {
        to_delete -= 1;
      }
    }
    return memo[pos][origin_to_delete] = result;
  }
public:
  int getLengthOfOptimalCompression(string s, int k) {
    this->s = s;
    memset(memo, -1, sizeof(memo[0]) * (s.length() + 1));
    return solve(0, k);
  }
};

// Accepted
// 136/136 cases passed (24 ms)
// Your runtime beats 97.73 % of cpp submissions
// Your memory usage beats 90.15 % of cpp submissions (6.3 MB)