String Compression II
Run-length encoding is a string compression method that works by replacing consecutive identical characters repeated 2 or more times with the concatenation of the character and the number marking the count of the characters, which is the length of the run.
Notice that in this problem, we are not adding '1' after single characters.
Given a string s and an integer k, delete at most k characters from s such that the run-length encoded version of s has minimum length.
Return the minimum length of the run-length encoded version of s after deleting at most k characters.
Example 1
Input
s = "aaabcccd", k = 2Output
4Deleting
b and d makes the compressed version "a3c3", which has length 4 and is optimal.Example 2
Input
s = "aabbaa", k = 2Output
2Deleting both
b characters leaves "aaaa", whose compressed form is "a4" with length 2.Constraints
- 1 <= s.length <= 100
- 0 <= k <= s.length
- s contains only lowercase English letters.