[LeetCode] 1531. String Compression II

Link here

I thought it should be Greedy at first, but was stuck in Example 2. Then, I considered about DP, but found it hard to figure out how to build the larger solution from the sub-problem.

So, another time I reached out for solution.

We use dp[i][j] to represent the minimum length of the first i letters after compression and after j deletions.

It obvious that if we delete the i-th letter, and then dp[i][j] = dp[i-1][j-1].

If we don’t, we can scan the former string sequence to try to “combine” the letters.

Time complexity: $O(n^2k)$

class Solution {
public:
    int getLengthOfOptimalCompression(string s, int k) {
        int n = s.length(); 
        vector<vector<int>> dp(n + 5, vector<int>(k + 5, 2e9)); 

        dp[0][0] = 0; 
        for (int i = 1; i <= n; ++i) {
            for (int j = 0; j <= min(n, k); ++j) {
                if (j > 0) dp[i][j] = dp[i - 1][j - 1]; 

                int del = 0, lasting_length = 0; 
                for (int h = i; h >= 1; --h) {
                    if (s[h - 1] == s[i - 1]) {
                        lasting_length++; 
                    }
                    else {
                        del++; 
                    }
                    if (del > j) break; 
                    if (lasting_length == 1)
                        dp[i][j] = min(dp[i][j], dp[h - 1][j - del] + 1);
                    else if (lasting_length <= 9)
                        dp[i][j] = min(dp[i][j], dp[h - 1][j - del] + 2);
                    else if (lasting_length <= 99)
                        dp[i][j] = min(dp[i][j], dp[h - 1][j - del] + 3);
                    else
                        dp[i][j] = min(dp[i][j], dp[h - 1][j - del] + 4); 
                }
            }
        }

        return dp[n][k]; 
    }
};