<p><a href="http://en.wikipedia.org/wiki/Run-length_encoding">Run-length encoding</a> 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>&quot;aabccc&quot;</code>&nbsp;we replace <font face="monospace"><code>&quot;aa&quot;</code></font>&nbsp;by&nbsp;<font face="monospace"><code>&quot;a2&quot;</code></font>&nbsp;and replace <font face="monospace"><code>&quot;ccc&quot;</code></font>&nbsp;by&nbsp;<font face="monospace"><code>&quot;c3&quot;</code></font>. Thus the compressed string becomes <font face="monospace"><code>&quot;a2bc3&quot;</code>.</font></p>

<p>Notice that in this problem, we are not adding&nbsp;<code>&#39;1&#39;</code>&nbsp;after single characters.</p>

<p>Given a&nbsp;string <code>s</code>&nbsp;and an integer <code>k</code>. You need to delete <strong>at most</strong>&nbsp;<code>k</code> characters from&nbsp;<code>s</code>&nbsp;such that the run-length encoded version of <code>s</code>&nbsp;has minimum length.</p>

<p>Find the <em>minimum length of the run-length encoded&nbsp;version of </em><code>s</code><em> after deleting at most </em><code>k</code><em> characters</em>.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

<pre>
<strong>Input:</strong> s = &quot;aaabcccd&quot;, k = 2
<strong>Output:</strong> 4
<b>Explanation: </b>Compressing s without deleting anything will give us &quot;a3bc3d&quot; of length 6. Deleting any of the characters &#39;a&#39; or &#39;c&#39; would at most decrease the length of the compressed string to 5, for instance delete 2 &#39;a&#39; then we will have s = &quot;abcccd&quot; which compressed is abc3d. Therefore, the optimal way is to delete &#39;b&#39; and &#39;d&#39;, then the compressed version of s will be &quot;a3c3&quot; of length 4.</pre>

<p><strong class="example">Example 2:</strong></p>

<pre>
<strong>Input:</strong> s = &quot;aabbaa&quot;, k = 2
<strong>Output:</strong> 2
<b>Explanation: </b>If we delete both &#39;b&#39; characters, the resulting compressed string would be &quot;a4&quot; of length 2.
</pre>

<p><strong class="example">Example 3:</strong></p>

<pre>
<strong>Input:</strong> s = &quot;aaaaaaaaaaa&quot;, k = 0
<strong>Output:</strong> 3
<strong>Explanation: </strong>Since k is zero, we cannot delete anything. The compressed string is &quot;a11&quot; of length 3.
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>1 &lt;= s.length &lt;= 100</code></li>
	<li><code>0 &lt;= k &lt;= s.length</code></li>
	<li><code>s</code> contains only lowercase English letters.</li>
</ul>

class Solution {
public:
    int getLengthOfOptimalCompression(string s, int k) {
        // vector<vector<pair<int, pair<int, char>>>> dp(k+1, vector<pair<int, pair<int, char>>> 
        //                                              (s.size(), make_pair(0, make_pair(0, '.'))));

        // char cur_char='.'; int cur_char_cnt=0, cur_cnt=0; 
        // for(int i=s.size()-1; i>=0; i--){
        //     if(s[i]!=cur_char){
        //         cur_cnt += 1,
        //         cur_char = s[i],
        //         cur_char_cnt = 1;
        //     } else{
        //         cur_char_cnt++;
        //         if(cur_char_cnt==10)
        //             cur_cnt += 1;
        //         if(cur_char_cnt==2)
        //             cur_cnt += 1;
        //     }
        //     dp[0][i] = make_pair(cur_cnt, make_pair(cur_char_cnt, cur_char));
        // }

        // int  u_cnt, r_cnt, dig, cnt;
        // for(int i=1; i<=k; i++){
        //     for(int j=s.size()-1-i; j>=0; j--){
        //         u_cnt = dp[i-1][j+1].first;
        //         dig   = (dp[i][j+1].second.first == 9 || dp[i][j+1].second.first == 1) ? 1 : 0;
        //         cnt   = (s[j] == dp[i][j+1].second.second) ? dp[i][j+1].second.first+1 : 1;
        //         r_cnt = (s[j] == dp[i][j+1].second.second) ? dp[i][j+1].first+dig : dp[i][j+1].first+1;

        //         if(u_cnt < r_cnt){

        //             dp[i][j] = make_pair(u_cnt, dp[i-1][j+1].second);

        //         } else if(u_cnt > r_cnt){

        //             dp[i][j] = make_pair(r_cnt, make_pair(cnt, s[j]));

        //         } else{

        //             if(j>0 && s[j] == s[j-1]){
        //                 dp[i][j] = make_pair(r_cnt, make_pair(cnt, s[j]));
        //             } else{
        //                 dp[i][j] = make_pair(u_cnt, dp[i-1][j+1].second);
        //             }

        //         }
                
        //     }
        // }
        // return dp[k][0].first;
        int n = s.size();
       
        vector<vector<int>> dp(n + 1, vector<int>(k + 1, INT_MAX));
        for(int i=0; i<=k; i++)
            dp[0][i]=0; 

        auto lengthOfCount = [](int count) {
            if (count == 1) return 0;      
            else if (count < 10) return 1;  
            else if (count < 100) return 2; 
            else return 3;                  
        };

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

                int count = 0, deletions = 0;
                for (int x = i; x <= n; ++x) {
                    if (s[x - 1] == s[i - 1]) {
                        count++;
                    } else {
                        deletions++;
                    }

                    if (j + deletions <= k) {
                        dp[x][j + deletions] = min(dp[x][j + deletions], 
                                                   dp[i - 1][j] + 1 + lengthOfCount(count));
                    }
                }

                if (j + 1 <= k) {
                    dp[i][j + 1] = min(dp[i][j + 1], dp[i-1][j]);
                }
            }
        }

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