Smallest length string with repeated replacement of two distinct adjacent | Java 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
import java . io . * ; class GFG { static int MAX_LEN = 110 ; static int [ ] [ ] [ ] DP = new int [ MAX_LEN ] [ MAX_LEN ] [ MAX_LEN ] ; static int length ( int a , int b , int 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 ] ; } static int stringReduction ( String str ) { int n = str . length ( ) ; int [ ] count = new int [ 3 ] ; for ( int i = 0 ; i < n ; ++ i ) count [ str . charAt ( i ) - ' a ' ] ++ ; for ( int i = 0 ; i <= count [ 0 ] ; ++ i ) for ( int j = 0 ; j < count [ 1 ] ; ++ j ) for ( int k = 0 ; k < count [ 2 ] ; ++ k ) DP [ i ] [ j ] [ k ] = - 1 ; return length ( count [ 0 ] , count [ 1 ] , count [ 2 ] ) ; } public static void main ( String [ ] args ) { String str = " abcbbaacb " ; System . out . println ( stringReduction ( str ) ) ; } }