Strings with long blocks of repeating characters take much less space if kept in a compressed representation. To obtain the compressed representation, we replace each segment of equal characters in the string with the number of characters in the segment followed by the character (for example, we replace segment "CCCC" with "4C"). To avoid increasing the size, we leave the one-letter segments unchanged (the compressed representation of "BC" is the same string - "BC").
For example, the compressed representation of the string "ABBBCCDDDCCC" is "A3B2C2D3C", and the compressed representation of the string "AAAAAAAAAABXXAAAAAAAAAA" is "11AB2X10A".
Observe that, in the second example, if we removed the "BXX" segment from the middle of the word, we would obtain a much shorter compressed representation - "21A". In order to take advantage of this observation, we decided to modify our compression algorithm.
Now, before compression, we remove exactly K consecutive letters from the input string. We would like to know the shortest compressed form that we can generate this way.
Given a string S of length N and an integer K, returns the shortest possible length of the compressed representation of S after removing exactly K consecutive characters from S.
Example 1:
Input: S = "ABBBCCDDCCC", K = 3
Output: 5
Explanation:After removing "DDC" from S, we are left with "ABBBCCC", which compresses to a representation of length 5 - "A3B4C".
Example 2:
Input: S = "AAAAAAAAAABXXAAAAAAAAAA", K = 3
Output: 3
Explanation:After removing "BXX" from S, we are left with "AAAAAAAAAAAAAAAAAAAAA", which compresses to a representation of length 3 - "21A".
Example 3:
Input: S = "ABCDDDEFG", K = 2
Output: 6
Explanation:After removing "EF" from S, we are left with "ABCDDDG", which compresses to a representation of length 6 - "ABC3DG".
- N is an integer within the range [1..1,000,000];
- K is an integer within the range [0..100,000];
- K ≤ N;
- string S is made only of uppercase letters (A-Z).
input:
output: