Minimum Length Of Compressed String

Ninja
0/200
Average time to solve is 60m
profile
Contributed by
26 upvotes
Asked in company
Amdocs

Problem statement

Run-length Encoding is the string compression technique that compresses the given string by replacing the number of consecutive identical characters (repeated 2 or more times) with the concatenation of the character and its count of characters.

For Example :

If the given string is  “wwwmpp”, then, Run-length encoded string will be “w3mp2”,
Here, we replace ‘www’ with ‘w3’, as the frequency of ‘w’ is 3, 
And, we replace ‘pp’ with ‘p2’, as the frequency of ‘p’ is 2, 
Thus, the given string is compressed to “w3mp2”, 
Note, for ‘m’ we are not adding 1 because it is mentioned in the definition of Run-Length Encoding, only 2 or more repeated character count will be concatenated.

You are given a string 'Str' and an integer 'K'. Your task is to find the minimum possible length of the run-length encoded string, which can be generated by deleting at most 'K' characters from the string 'Str'.

For Example :

Consider the string 'Str' = “cccdeeef” and 'K' =2, 
Current Run-length encoded string is "c3de3f" having length 6. 
Here we can delete at most 2 characters, so If we delete any of the characters 'c' or 'e', it would at most decrease the length of the compressed string to 5, 
For example, if we delete 2 'c' then we will have the string "cdeeef" which can be compressed to “cde3f”. Therefore, the optimal way is to delete 'd' and 'f', then the compressed string will be "c3e3" of length 4.
Detailed explanation ( Input/output format, Notes, Images )

Input Format :

The first line of input contains a single integer 'T', representing the number of test cases or queries to be run. 

Then the 'T' test cases follow.

The first line of each test case contains a string 'STR'.

The second line of each test case contains a single integer 'K', representing the maximum deletions allowed in the string.

Output Format :

For each test case, print the length of the minimum compressed string after deleting at-most 'K' characters in a separate line.

Note :

You do not need to print anything, it has already been taken care of. Just implement the given function.

Constraints :

1 <= T <= 50    
1 <= |STR| <= 100 
0 <= K <= |STR|   

Where |STR| denotes the length of string 'STR'.
All the characters of the string will be in lowercase


Time Limit: 1 sec
Sample Input 1 :
2
cccdeeef
2
goofood
1
Sample Output 1 :
4
4
Explanation For Sample Output 1 :
Test Case 1:
Here 'Str' = “cccdeeef” and K = 2.
The current Run-length encoded string is "c3de3f"  and its length is 6, and we can delete at most 2 characters. 
If we delete any of the characters 'c' or 'e', it would at most decrease the length of the compressed string to 5. For example, if we delete 2 'c' then we will have the string "cdeeef" which can be compressed to “cde3f”. 
The optimal way is to delete 'd' and 'f', then the compressed string will be "c3e3" of length 4.

Test Case: 2
Here ‘Str’ = “goofood”, and  K=1.
The current Run-length encoded string is “go2do2f” and its length is 7, and we can delete at most 1 character. 
If we remove ‘g’ or ‘f’,  it would at most decrease the length of the compressed string to 6. 
For example, if we delete 'g' then we will have Str = "oodoof" which can be compressed to “o2do2f”. If we delete any of the ‘o’, then we will have Str = “godoof”, compressed to “godo2f”, of length 6. 
The most optimal way is to delete ‘d’, then the compressed string will be "go4f" of length 4.
Sample Input 2 :
2
aabbaa
3
abcde
0
Sample Output 2 :
2
5
Hint

Find all possible strings that can be obtained by deleting at most ‘K’ characters.

Approaches (3)
Brute Force

We find all possible strings that can be obtained by deleting at most ‘K’ characters using a backtracking algorithm. Then one by one we compress all these strings and find the minimum length after compression.

 

Algorithm

  • Create an empty list of strings ‘possibleStr’.
  • Create an empty string ‘curStr’.
  • Call a function findPossibleString(possibleStr, curStr, K, curIdx) Where ‘K’ is the number of deletion allowed and curIdx represents the current Index of string ‘str’. This function will backtrack to generate all possible strings as follows
    • If curIdx = length of given string ‘Str’,  then append curStr in list possibeStr and then return.
    • Otherwise if K > 0 then call findPossibleString(possibleStr, curStr, K-1, curIdx+1) to find possible string after removal of current character.
    • And append Str[curIdx] in curStr, and then call findPossibleString(possibleStr, curStr, K, curIdx+1) to find all possible strings after retention of current character.
    • Remove this character from curStr.
  • List ‘possibleStr’ will now have all possible strings that can be obtained after removing at most ‘K’ characters.
  • Initialize an integer variable  ‘result’ by infinity.
  • Iterate over the list ‘possibleStr’ and compress each string of this list as follows.
    • Initialize a variable ‘cnt’ := 0.
    • Create an empty string ‘compressedStr’.
    • Traverse over the string and if the current character is the same as the previous character then increment ‘cnt’ by ‘1’  otherwise, append the current character with ‘cnt’ in  ‘compressedStr’ and change ‘cnt’ value to  1.
    • Update result with a minimum of its current value and length of ‘compressedStr’.
  • Return ‘result’.
Time Complexity

O(N*2^N), where N is the length of the given string.  

 

In the worst-case i.e when K = N, the number of strings in possibleStr will be 2^N. Compressing each string takes linear time, thus total complexity will be O(N*2^N)

.

Space Complexity

O(N*2^N), where N is the length of the given string.  

 

In the worst-case i.e when K = N, the number of strings in possibleStr will be 2^N and the length of each string will be of the order of N. Thus overall extra space used is of the order of O(N*2^N),

Code Solution
(100% EXP penalty)
Minimum Length Of Compressed String
Full screen
Console