Minimum length of Run Length Encoding possible by removing at most K characters from a given string | Java 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
import java . util . * ; 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 . charAt ( idx ) ) { ans = Math . min ( ans , inc + solve ( s , n , idx + 1 , k , s . charAt ( idx ) , count + 1 ) ) ; } else { ans = Math . min ( ans , 1 + solve ( s , n , idx + 1 , k , s . charAt ( idx ) , 1 ) ) ; } return dp [ idx ] [ k ] [ last - ' a ' ] [ count ] = ans ; } public static int MinRunLengthEncoding ( String s , int n , int k ) { for ( int i [ ] [ ] [ ] : dp ) for ( int j [ ] [ ] : i ) for ( int p [ ] : j ) Arrays . fill ( p , - 1 ) ; return solve ( s , n , 0 , k , ( char ) 123 , 0 ) ; } public static void main ( String args [ ] ) { String S = " abbbcdcdd " ; int N = 9 , K = 2 ; System . out . println ( MinRunLengthEncoding ( S , N , K ) ) ; } }