Smallest length string with repeated replacement of two distinct adjacent | Javascript program to find smallest possible length of a string of only three characters ; Program to find length of reduced string in a string made of three characters . ; A memoized function find result recursively . a , b and c are counts of ' a ' s , ' b ' s and ' c ' s in str ; If this subproblem is already evaluated ; If this subproblem is already evaluated ; If there is only one type of character ; If only two types of characters are present ; If all types of characters are present . Try combining all pairs . ; Returns smallest possible length with given operation allowed . ; Counting occurrences of three different characters ' a ' , ' b ' and ' c ' in str ; Initialize DP [ ] [ ] entries as - 1 ; Driver code
let MAX_LEN = 110 ; let DP = new Array ( MAX_LEN ) ; for ( let i = 0 ; i < DP . length ; i ++ ) { DP [ i ] = new Array ( MAX_LEN ) ; for ( let j = 0 ; j < DP [ i ] . length ; j ++ ) { DP [ i ] [ j ] = new Array ( MAX_LEN ) ; for ( let k = 0 ; k < MAX_LEN ; k ++ ) { DP [ i ] [ j ] [ k ] = 0 ; } } } function length ( a , b , c ) { if ( a < 0 b < 0 c < 0 ) if ( DP [ a ] [ b ] != - 1 ) return DP [ a ] [ b ] ; if ( a == 0 && b == 0 ) return ( DP [ a ] [ b ] = c ) ; if ( a == 0 && c == 0 ) return ( DP [ a ] [ b ] = b ) ; if ( b == 0 && c == 0 ) return ( DP [ a ] [ b ] = a ) ; if ( a == 0 ) return ( DP [ a ] [ b ] = length ( a + 1 , b - 1 , c - 1 ) ) ; if ( b == 0 ) return ( DP [ a ] [ b ] = length ( a - 1 , b + 1 , c - 1 ) ) ; if ( c == 0 ) return ( DP [ a ] [ b ] = length ( a - 1 , b - 1 , c + 1 ) ) ; DP [ a ] [ b ] = Math . min ( length ( a - 1 , b - 1 , c + 1 ) , Math . min ( length ( a - 1 , b + 1 , c - 1 ) , length ( a + 1 , b - 1 , c - 1 ) ) ) ; return DP [ a ] [ b ] ; } function stringReduction ( str ) { let n = str . length ; let count = new Array ( 3 ) ; for ( let i = 0 ; i < 3 ; i ++ ) { count [ i ] = 0 ; } for ( let i = 0 ; i < n ; ++ i ) count [ str [ i ] . charCodeAt ( 0 ) - ' ' . charCodeAt ( 0 ) ] ++ ; for ( let i = 0 ; i <= count [ 0 ] ; ++ i ) for ( let j = 0 ; j < count [ 1 ] ; ++ j ) for ( let k = 0 ; k < count [ 2 ] ; ++ k ) DP [ i ] [ j ] [ k ] = - 1 ; return length ( count [ 0 ] , count [ 1 ] , count [ 2 ] ) ; } let str = " " ; document . write ( stringReduction ( str ) ) ;