Minimum length of Run Length Encoding possible by removing at most K characters from a given string | Python3 program to implement the above approach ; Function which solves the desired problem ; Base Case ; If the entire string has been traversed ; If precomputed subproblem occurred ; Minimum run length encoding by removing the current character ; Minimum run length encoding by retaining the current character ; If the current and the previous characters match ; Otherwise ; Function to return minimum run - length encoding for string s by removing atmost k characters ; Driver Code
maxN = 20 NEW_LINE dp = [ [ [ [ 0 for i in range ( maxN ) ] for j in range ( 27 ) ] for k in range ( 27 ) ] for l in range ( maxN ) ] NEW_LINE def solve ( s , n , idx , k , last , count ) : NEW_LINE INDENT if ( k < 0 ) : NEW_LINE INDENT return n + 1 NEW_LINE DEDENT if ( idx == n ) : NEW_LINE INDENT return 0 NEW_LINE DEDENT ans = dp [ idx ] [ k ] [ ord ( last ) - ord ( ' a ' ) ] [ count ] NEW_LINE if ( ans != - 1 ) : NEW_LINE INDENT return ans NEW_LINE DEDENT ans = n + 1 NEW_LINE ans = min ( ans , solve ( s , n , idx + 1 , k - 1 , last , count ) ) NEW_LINE inc = 0 NEW_LINE if ( count == 1 or count == 9 or count == 99 ) : NEW_LINE INDENT inc = 1 NEW_LINE DEDENT if ( last == s [ idx ] ) : NEW_LINE INDENT ans = min ( ans , inc + solve ( s , n , idx + 1 , k , s [ idx ] , count + 1 ) ) NEW_LINE DEDENT else : NEW_LINE INDENT ans = max ( ans , 1 + solve ( s , n , idx + 1 , k , s [ idx ] , 1 ) ) NEW_LINE DEDENT dp [ idx ] [ k ] [ ord ( last ) - ord ( ' a ' ) ] [ count ] = ans NEW_LINE print ( ans ) NEW_LINE return dp [ idx ] [ k ] [ ord ( last ) - ord ( ' a ' ) ] [ count ] NEW_LINE DEDENT def MinRunLengthEncoding ( s , n , k ) : NEW_LINE INDENT for i in range ( maxN ) : NEW_LINE INDENT for j in range ( 27 ) : NEW_LINE INDENT for k in range ( 27 ) : NEW_LINE INDENT for l in range ( maxN ) : NEW_LINE INDENT dp [ i ] [ j ] [ k ] [ l ] = - 1 NEW_LINE DEDENT DEDENT DEDENT DEDENT return solve ( s , n , 0 , k , chr ( 123 ) , 0 ) - 1 NEW_LINE DEDENT if __name__ == ' _ _ main _ _ ' : NEW_LINE INDENT S = " abbbcdcdd " NEW_LINE N = 9 NEW_LINE K = 2 NEW_LINE print ( MinRunLengthEncoding ( S , N , K ) ) NEW_LINE DEDENT