Minimum Length Of Compressed String

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’.

Let Len(curIdx, K, prevChar, cntPrevChar) denote the minimum run-length-encoding obtained starting from index curIdx where K denotes the number of deletions remaining, prevChar denotes the last character with frequency cntPrevChar so far.

Now two possibilities exist, either to delete the current character or to retain it.

If K > 0 and we delete the current character then -:

L1 = Len(curIdx+1, K-1, prevChar, cntPrevChar)

If we retain the current character then there are two possible cases -:

1. If prevChar and current character are the same, then

            L2 = Len(curIdx+1, K, prevChar, cntPrevChar+1)

1. If prevChar and Current character are not the same, then

            L2 = Len(curIdx+1, K, current character, 1)

Len(curIdx, K, prevChar, cntPrevChar) = min(L1, L2).

Algorithm

• Create a function  helper(curIdx, K, prevChar, cntPrevChar) where
  • curIdx: current index in str.
  • K: Remaining number of deletions.
  • prevChar: previous character.
  • cntPrevChar: Number of occurrences of the previous character.
• The function can be implemented recursively as follows -:
  • If the entire string has been traversed i.e curIdx = N, then return 0, because there is no more character so no further addition will be in length.
  • If K > 0 then call helper(curIdx+1, K-1, prevChar, cntPrevChar); It will give a minimum run-length encoding by removing the current character. Store this value in the integer variable ‘result’.
  • If Str[curIdx] == prevChar then call helper(curIdx+1, K, prevChar, cntPrevChar+1), Otherwise call helper(curIdx+1, K, Str[curIdx], 1). The minimum run-length encoding by retaining the current character will be helper(curIdx+1, K, Str[curIdx], 1) + 1 if Str[curIdx] != prevChar, otherwise it will be helper(curIdx+1, K, prevChar, cntPrevChar+1) + 1 when cntPrevChar is 2, 9 or 99 as number of digits increment by 1, and helper(curIdx+1, K, prevChar, cntPrevChar+1) for all other values of cntPrevChar.  Update result with maximum of its previous value and this value.
  • Return ‘result’.
• We will call helper(0, K, #, 0) to calculate the minimum length of the compressed string (minimum run-length encoding) of the given string.  Note here ‘#’ is the character that symbolizes the start of the string.

In the previous approach, we can observe that we have done a lot of repeated work. To avoid repeated work we will store the result of already computed subproblems in a ‘dp’ table.  

The ‘dp’ table will have four dimension dp[curIdx][K][prevChar][cntPrevChar] where curIdx: current index in, K: Remaining number of deletion, prevChar: a previous character we represent a character with an integer between 1 to 26., cntPrevChar: Number of occurrences of the previous character.

Algorithm

• Create a ‘dp’ table of dimension N*K*26*N and fill it by -1.
• Create a function  helper(curIdx, K, prevChar, cntPrevChar) where
  • curIdx: current index in str.
  • K: Remaining number of deletions.
  • prevChar: previous character (represented by an integer).
  • cntPrevChar: Number of occurrences of the previous character.
• The function can be implemented recursively as follows -:
  • If the entire string has been traversed i.e curIdx = N, then return 0, because there is no more character so no further addition will be in length.
  •  If dp[curIdx][K][prevChar][cntPrevChar] != -1,  i.e the subproblem is already computed so be return its result then simply return it.
  • If K > 0 then call helper(curIdx+1, K-1, prevChar, cntPrevChar); It will give a minimum run-length encoding by removing the current character. Store this value in the integer variable ‘result’.
  • If Str[curIdx] - ‘a’ == prevChar then call helper(curIdx+1, K, prevChar, cntPrevChar+1), Otherwise call helper(curIdx+1, K, Str[curIdx] - ‘a’, 1). The minimum run-length encoding by retaining the current character will be helper(curIdx+1, K, Str[curIdx] - ‘a’, 1) + 1 if Str[curIdx] -’a’!= prevChar, otherwise it will be helper(curIdx+1, K, prevChar, cntPrevChar+1) + 1 when cntPrevChar is 2, 9 or 99 as number of digits increment by 1, and helper(curIdx+1, K, prevChar, cntPrevChar+1) for all other values of cntPrevChar.  Update result with maximum of its previous value and this value.
  • Store ‘result’ in dp[curIdx][K][prevChar][cntPrevChar].
  • Return ‘result’. 
• We will call a helper(0, K, 27, 0) to calculate the minimum length of the compressed string (minimum run-length encoding) of the given string.  Note here 27 is the integer representation of the character that symbolizes the start of the string.