#1531
String Compression II
candidate master · 1370 · lc hard +32 · verified · 52.2% accepted · 2,509 likes · top 42%
Description
Run-length encoding compresses consecutive duplicate characters — a run of character c of length L >= 2 becomes "cL" (single characters are written without a count). Given string s and integer k, delete at most k characters from s to minimize the length of its run-length encoded representation. Return that minimum length.
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.
Code
1
2
3