# 1531. String Compression II
## Problem Statement
[Run-length encoding](http://en.wikipedia.org/wiki/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 (length of the run). For example, to compress the string `"aabccc"` we replace `"aa"` by `"a2"` and replace `"ccc"` by `"c3"`. Thus the compressed string becomes `"a2bc3"`.
Notice that in this problem, we are not adding `'1'` after single characters.
Given a string `s` and an integer `k`. You need to delete **at most** `k` characters from `s` such that the run-length encoded version of `s` has minimum length.
Find the *minimum length of the run-length encoded version of* `s` *after deleting at most* `k` *characters*.
**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.
**Constraints:**
* `1 <= s.length <= 100`
* `0 <= k <= s.length`
* `s` contains only lowercase English letters.
## Intuition
```
Approach:
We keep track of Previous character and previous streak of same lenght
To keep track of the actual length
thereFore, when we notake= we delete it so prevchar does not change,
Streak remains same
But when take the char and not delete it,
if same, We len increases at 1,9,99; also streak increases
If not same, streak reset and lenght added of first char, eg aa | bb
b starts b2 so 1st lenght is added for b, hence +1
```
### Links
### Video Links
\
\
### Approach 1:
```
```
{% code title="C++" lineNumbers="true" %}
```cpp
int dp[101][101][27][101] ;
class Solution {
private:
int solve(int i,int k,int prev,int prev_count,string &s){
if(k<0)
return 1e9;
if(i>=s.length())
return 0;
if(dp[i][k][prev][prev_count] !=-1)
return dp[i][k][prev][prev_count];
int take=INT_MAX;
int noTake = solve(i+1,k-1,prev,prev_count,s);
//If we do not take character then the length will remain same as previous
if(s[i] == prev+'a'){
int increment = (prev_count==1 || prev_count==9 || prev_count==99);
take = increment + solve(i+1,k,prev,prev_count+1,s);
}//a9(2 len) + a = a10 (3 len)
else{
take= 1 + solve(i+1, k, s[i]-'a', 1, s);
//When we insert any new character string length increased by 1;
}
return dp[i][k][prev][prev_count] = min(take,noTake);
}
public:
int getLengthOfOptimalCompression(string s, int K) {
memset(dp , -1, sizeof(dp)) ;
return solve(0,K,26,0,s);
}
};
```
{% endcode %}
### Approach 2:
```
```
{% code title="C++" lineNumbers="true" %}
```cpp
```
{% endcode %}
### Approach 3:
```
```
{% code title="C++" lineNumbers="true" %}
```cpp
```
{% endcode %}
### Approach 4:
```
```
{% code title="C++" lineNumbers="true" %}
```cpp
```
{% endcode %}
### Similar Problems
###
---
# Agent Instructions: Querying This Documentation
If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.
Perform an HTTP GET request on the current page URL with the `ask` query parameter:
```
GET https://coding-9.gitbook.io/untitled/string/hard/1531.-string-compression-ii.md?ask=
```
The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.
Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.