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
using System ; class GFG { static int maxN = 20 ; static int [ , , , ] dp = new int [ maxN , maxN , 27 , maxN ] ; public static int solve ( String s , int n , int idx , int k , char last , int count ) { 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 = Math . 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 = Math . Min ( ans , inc + solve ( s , n , idx + 1 , k , s [ idx ] , count + 1 ) ) ; } else { ans = Math . Min ( ans , 1 + solve ( s , n , idx + 1 , k , s [ idx ] , 1 ) ) ; } return dp [ idx , k , last - ' a ' , count ] = ans ; } public static int MinRunLengthEncoding ( String s , int n , int k ) { for ( int i = 0 ; i < maxN ; i ++ ) for ( int j = 0 ; j < maxN ; j ++ ) for ( int p = 0 ; p < 27 ; p ++ ) for ( int l = 0 ; l < maxN ; l ++ ) dp [ i , j , p , l ] = - 1 ; return solve ( s , n , 0 , k , ( char ) 123 , 0 ) ; } public static void Main ( String [ ] args ) { String S = " abbbcdcdd " ; int N = 9 , K = 2 ; Console . WriteLine ( MinRunLengthEncoding ( S , N , K ) ) ; } }