Minimum length of Run Length Encoding possible by removing at most K characters from a given string | JavaScript 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
let maxN = 20 ; let dp = new Array ( maxN ) ; function solve ( s , n , idx , k , last , count ) { if ( k < 0 ) return n + 1 ; if ( idx == n ) return 0 ; let ans = dp [ idx ] [ k ] [ last - ' ' . charCodeAt ( ) ] [ count ] ; if ( ans != - 1 ) return ans ; ans = n + 1 ; ans = Math . min ( ans , solve ( s , n , idx + 1 , k - 1 , last , count ) ) ; let inc = 0 ; if ( count == 1 count == 9 count == 99 ) inc = 1 ; if ( last == s [ idx ] . charCodeAt ( ) ) { ans = Math . min ( ans , inc + solve ( s , n , idx + 1 , k , s [ idx ] . charCodeAt ( ) , count + 1 ) ) ; } else { ans = Math . min ( ans , 1 + solve ( s , n , idx + 1 , k , s [ idx ] . charCodeAt ( ) , 1 ) ) ; } dp [ idx ] [ k ] [ last - ' ' . charCodeAt ( ) ] [ count ] = ans ; return dp [ idx ] [ k ] [ last - ' ' . charCodeAt ( ) ] [ count ] ; } function MinRunLengthEncoding ( s , n , k ) { for ( let i = 0 ; i < maxN ; i ++ ) { dp [ i ] = new Array ( maxN ) ; for ( let j = 0 ; j < maxN ; j ++ ) { dp [ i ] [ j ] = new Array ( 27 ) ; for ( let k = 0 ; k < 27 ; k ++ ) { dp [ i ] [ j ] [ k ] = new Array ( maxN ) ; for ( let l = 0 ; l < maxN ; l ++ ) { dp [ i ] [ j ] [ k ] [ l ] = - 1 ; } } } } return solve ( s , n , 0 , k , 123 , 0 ) ; } let S = " " ; let N = 9 , K = 2 ; document . write ( MinRunLengthEncoding ( S , N , K ) ) ;