Minimum length of Run Length Encoding possible by removing at most K characters from a given string | C ++ 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
#include <bits/stdc++.h> NEW_LINE using namespace std ; #define maxN  20 NEW_LINE int dp [ maxN ] [ maxN ] [ 27 ] [ maxN ] ; int solve ( string & s , int n , int idx , int k , char last = 123 , int count = 0 ) { if ( k < 0 ) return n + 1 ; if ( idx == n ) return 0 ; int & ans = dp [ idx ] [ k ] [ last - ' a ' ] [ count ] ; if ( ans != -1 ) return ans ; ans = n + 1 ; ans = min ( ans , solve ( s , n , idx + 1 , k - 1 , last , count ) ) ; int inc = 0 ; if ( count == 1 count == 9 count == 99 ) inc = 1 ; if ( last == s [ idx ] ) { ans = min ( ans , inc + solve ( s , n , idx + 1 , k , s [ idx ] , count + 1 ) ) ; } else { ans = min ( ans , 1 + solve ( s , n , idx + 1 , k , s [ idx ] , 1 ) ) ; } return ans ; } int MinRunLengthEncoding ( string & s , int n , int k ) { memset ( dp , -1 , sizeof ( dp ) ) ; return solve ( s , n , 0 , k ) ; } int main ( ) { string S = " abbbcdcdd " ; int N = 9 , K = 2 ; cout << MinRunLengthEncoding ( S , N , K ) ; return 0 ; }