Minimum replacements to make adjacent characters unequal in a ternary string | Set | Java program to count the minimal replacements such that adjacent characters are unequal ; function to return integer value of i - th character in the string ; Function to count the number of minimal replacements ; If the string has reached the end ; If the state has been visited previously ; Get the current value of character ; If it is equal then change it ; All possible changes ; Change done ; } else If same no change ; Driver Code ; Length of string ; Create a DP array ; First character ; Function to find minimal replacements
class GFG { static int charVal ( String s , int i ) { if ( s . charAt ( i ) == '0' ) { return 0 ; } else if ( s . charAt ( i ) == '1' ) { return 1 ; } else { return 2 ; } } static int countMinimalReplacements ( String s , int i , int prev , int dp [ ] [ ] , int n ) { if ( i == n ) { return 0 ; } if ( dp [ i ] [ prev ] != - 1 ) { return dp [ i ] [ prev ] ; } int val = charVal ( s , i ) ; int ans = Integer . MAX_VALUE ; if ( val == prev ) { val = 0 ; for ( int cur = 0 ; cur <= 2 ; cur ++ ) { if ( cur == prev ) { continue ; } val = 1 + countMinimalReplacements ( s , i + 1 , cur , dp , n ) ; ans = Math . min ( ans , val ) ; } { ans = countMinimalReplacements ( s , i + 1 , val , dp , n ) ; } return dp [ i ] [ val ] = ans ; } public static void main ( String [ ] args ) { String s = "201220211" ; int n = s . length ( ) ; int dp [ ] [ ] = new int [ n ] [ 3 ] ; for ( int i = 0 ; i < n ; i ++ ) { for ( int j = 0 ; j < 3 ; j ++ ) { dp [ i ] [ j ] = - 1 ; } } int val = charVal ( s , 0 ) ; System . out . println ( countMinimalReplacements ( s , 1 , val , dp , n ) ) ; } }