<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 solve1(string s, int k) {
      int n = s.size();

      // [removed][current][count]
      vector<vector<vector<int>>> dp(k + 1, vector<vector<int>>(26, vector<int>(n + 1, 1e9)));
      vector<vector<vector<int>>> next(k + 1, vector<vector<int>>(26, vector<int>(n + 1, 1e9)));

      dp[0][s[0] - 'a'][1] = 1;
      if (k > 0) {
        dp[1][s[0] - 'a'][0] = 0;
      }

      const auto get_increase = [&](int l) -> int {
        return (l == 2 || l == 10 || l == 100);
      };

      vector<int> best_removed(k + 1, 0);
      for (int i = 1; i < n; ++i) {
        const int max_removed = min(k, i + 1);
        const int max_count = i + 1;
        const int current = s[i] - 'a';
  
        for (int removed = 0; removed <= max_removed; ++removed) {
          best_removed[removed] = 1e9;
          for (int count = 0; count <= max_count; ++count) {
            for (int c = 0; c < 26; ++c) {
              next[removed][c][count] = 1e9;
              // when remove, keep the same results.
              if (removed > 0) {
                next[removed][c][count] = dp[removed - 1][c][count];
              }

              if (c != current) {
                best_removed[removed] = min(best_removed[removed], dp[removed][c][count]);
              }
            }
          }
        }

        for (int removed = 0; removed <= max_removed; ++removed) {
          // count when keep with a different symbol.
          next[removed][current][1] = min(next[removed][current][1], best_removed[removed] + 1);

          // count when keep with the same symbol.
          for (int count = 1; count <= max_count; ++count) {
            next[removed][current][count] = min(
              next[removed][current][count], 
              dp[removed][current][count - 1] + (count == 1 ? 1 : 0) + get_increase(count)
            );      
          }
        }

        next.swap(dp);
      }

      int ans = 1e9;
      for (int count = 0; count <= n; ++count) {
        for (int c = 0; c < 26; ++c) {
          ans = min(ans, dp[k][c][count]);
        }
      }
      

      return ans;
    }

    int solve2(string s, int k) {
      int n = s.size();

      vector<vector<pair<int, int>>> dp(k + 1, vector<pair<int, int>>(26, pair<int, int>(-1, 0)));
      vector<vector<pair<int, int>>> next(k + 1, vector<pair<int, int>>(26, pair<int, int>(-2, 1e9)));

      const auto get_increase = [&](int l) -> int {
        return (l == 2 || l == 10 || l == 100);
      };

      const auto get_distance_to_next_increase = [&](int l) -> int {
        if (l < 1) {
          return l - 1;
        } else if (l < 2) {
          return 2 - l;
        } else if (l < 10) {
          return 10 - l;
        } else {
          return 100 - l;
        }
      };

      const auto update_keep = [&](int current, int prev, int removed) -> void {
        pair<int, int> new_entry = dp[removed][prev];
        if (new_entry.first == -1) {
          new_entry = pair<int, int>(1, 1);
        } else if (new_entry.first >= 0) {
          if (prev != current) {
            new_entry.first = 1;
            new_entry.second += 1;
          } else {
            new_entry.first += 1;
            new_entry.second += get_increase(new_entry.first);
          }
        }

        if (new_entry.first >= 0) {
          int new_distance_to_increase = get_distance_to_next_increase(new_entry.second);
          int current_distance_to_increase = get_distance_to_next_increase(next[removed][current].second);

          if (new_entry.second < next[removed][current].second) {
            next[removed][current] = new_entry;
          } else if (new_entry.second == next[removed][current].second && current == prev) {
            next[removed][current] = new_entry;
          } else if (new_entry.second == next[removed][current].second && (new_distance_to_increase > current_distance_to_increase)) {
            next[removed][current] = new_entry;
          }
        }
      };

      const auto update_remove = [&](int current, int prev, int removed) -> void {
        pair<int, int> new_entry = dp[removed - 1][prev];
        if (new_entry.first == -1) {
          next[removed][current] = new_entry;
        } else if (new_entry.first >= 0 && new_entry.second < next[removed][prev].second) {
          int new_distance_to_increase = get_distance_to_next_increase(new_entry.second);
          int current_distance_to_increase = get_distance_to_next_increase(next[removed][current].second);
          if (new_entry.second < next[removed][current].second) {
            next[removed][current] = new_entry;
          } else if (new_entry.second == next[removed][current].second && (new_distance_to_increase > current_distance_to_increase)) {
            next[removed][current] = new_entry;
          }
        }
      };

      for (int i = 0; i < n; ++i) {
        for (int removed = 0; removed <= k; ++removed) {
          for (int c = 0; c < 26; ++c) {
            next[removed][c] = pair<int, int>(-2, 1e9);
          }
        }

        for (int removed = 0; removed <= min(k, i + 1); ++removed) {
          for (int prev = 0; prev < 26; ++prev) {
            update_keep(s[i] - 'a', prev, removed);
            if (removed > 0) {
              update_remove(s[i] - 'a', prev, removed);
            }
          }
        }

        // for (int removed = 0; removed <= k; ++removed) {
        //   for (int prev = 0; prev < 26; ++prev) {
        //     if (next[removed][prev].first >= -1) {
        //       cout << "i = " << i << "(" << s[i] << "), removed = " << removed << ", prev = " << char('a' + prev) << " = " << next[removed][prev].first << ", " << next[removed][prev].second << endl;
        //     }
        //   }
        // }

        next.swap(dp);
      }

      int ans = 1e9;
      for (int c = 0; c < 26; ++c) {
        ans = min(ans, dp[k][c].second);
      }

      return ans;
    }


    int solve3(string s, int k) {
      int n = s.size();

      // [removed][current][count]
      vector<vector<vector<int>>> dp(k + 1, vector<vector<int>>(26, vector<int>(n + 1, 1e9)));

      dp[0][s[0] - 'a'][1] = 1;
      if (k > 0) {
        dp[1][s[0] - 'a'][0] = 0;
      }

      const auto get_increase = [&](int l) -> int {
        return (l == 2 || l == 10 || l == 100);
      };

      vector<int> count_by(26, 0);
      for (int i = 1; i < n; ++i) {
        const int max_removed = min(k, i + 1);
        const int max_count = i + 1;
        const int current = s[i] - 'a';
        count_by[current] += 1;
  
        for (int removed = max_removed; removed >= 0; --removed) {
          // best_removed[removed] = 1e9;
          int best_removed = 1e9;
          for (int c = 0; c < 26; ++c) {
            for (int count = max_count; count >= 0; --count) {
              if (c == current) {
                // count when keep with the same symbol.
                if (count > 0) {
                  dp[removed][current][count] = dp[removed][current][count - 1] + (count == 1 ? 1 : 0) + get_increase(count);              
                } else {
                  dp[removed][current][count] = 1e9;
                }
              }

              if (c != current) {
                best_removed = min(best_removed, dp[removed][c][count]);
                dp[removed][c][count] = 1e9;
              }
            
              // when remove, keep the same results.
              if (removed > 0) {
                dp[removed][c][count] = min(dp[removed][c][count], dp[removed - 1][c][count]);
              }
            }
          }

          dp[removed][current][1] = min(dp[removed][current][1], best_removed + 1);
        }
      }

      int ans = 1e9;
      for (int count = 0; count <= n; ++count) {
        for (int c = 0; c < 26; ++c) {
          ans = min(ans, dp[k][c][count]);
        }
      }
      

      return ans;
    }

    int getLengthOfOptimalCompression(string s, int k) {
      // return solve1(s, k);
      // return solve2(s, k);
      return solve3(s, k);
    }
};
52300