string-compression-ii

java

python

python3

mysql

mssql

oraclesql

csharp

javascript

typescript

bash

swift

kotlin

dart

golang

ruby

scala

rust

racket

erlang

elixir

pythondata

postgresql

cangjie

Algorithms

<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 <code>&quot;aa&quot;</code>&nbsp;by&nbsp;<code>&quot;a2&quot;</code>&nbsp;and replace <code>&quot;ccc&quot;</code>&nbsp;by&nbsp;<code>&quot;c3&quot;</code>. Thus the compressed string becomes <code>&quot;a2bc3&quot;</code>.

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

Given a&nbsp;string <code>s</code>&nbsp;and an integer <code>k</code>. You need to delete at most&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.

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

&nbsp;
Example 1:

<pre>
Input: s = &quot;aaabcccd&quot;, k = 2
Output: 4
Explanation: 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>

Example 2:

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

Example 3:

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

&nbsp;
Constraints:

<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>

getLengthOfOptimalCompression

String Compression II

String Compression III

string-compression-iii

压缩字符串 III

String

Dynamic Programming

<a href="https://baike.baidu.com/item/%E8%A1%8C%E7%A8%8B%E9%95%BF%E5%BA%A6%E7%BC%96%E7%A0%81/2931940?fr=aladdin" target="_blank">行程长度编码</a> 是一种常用的字符串压缩方法，它将连续的相同字符（重复 2 次或更多次）替换为字符和表示字符计数的数字（行程长度）。例如，用此方法压缩字符串 <code>&quot;aabccc&quot;</code> ，将 <code>&quot;aa&quot;</code> 替换为 <code>&quot;a2&quot;</code> ，<code>&quot;ccc&quot;</code> 替换为` <code>&quot;c3&quot;</code> 。因此压缩后的字符串变为 <code>&quot;a2bc3&quot;</code> 。

注意，本问题中，压缩时没有在单个字符后附加计数 <code>&#39;1&#39;</code> 。

给你一个字符串 <code>s</code> 和一个整数 <code>k</code> 。你需要从字符串 <code>s</code> 中删除最多 <code>k</code> 个字符，以使 <code>s</code> 的行程长度编码长度最小。

请你返回删除最多 <code>k</code> 个字符后，<code>s</code> 行程长度编码的最小长度 。

&nbsp;

示例 1：

<pre>输入：s = &quot;aaabcccd&quot;, k = 2
输出：4
解释：在不删除任何内容的情况下，压缩后的字符串是 &quot;a3bc3d&quot; ，长度为 6 。最优的方案是删除 &#39;b&#39; 和 &#39;d&#39;，这样一来，压缩后的字符串为 &quot;a3c3&quot; ，长度是 4 。</pre>

示例 2：

<pre>输入：s = &quot;aabbaa&quot;, k = 2
输出：2
解释：如果删去两个 &#39;b&#39; 字符，那么压缩后的字符串是长度为 2 的 &quot;a4&quot; 。
</pre>

示例 3：

<pre>输入：s = &quot;aaaaaaaaaaa&quot;, k = 0
输出：3
解释：由于 k 等于 0 ，不能删去任何字符。压缩后的字符串是 &quot;a11&quot; ，长度为 3 。
</pre>

&nbsp;

提示：

<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> 仅包含小写英文字母</li>
</ul>