Minimum replacements such that the difference between the index of the same characters is divisible by 3 | Java program to find minimum replacements such that the difference between the index of the same characters is divisible by 3 ; Function to count the number of minimal replacements ; Generate all permutations ; Count the replacements ; Return the replacements ; Driver Code
class GFG { static int countMinimalReplacements ( String s ) { int n = s . length ( ) ; int mini = Integer . MAX_VALUE ; char [ ] dup = "012" . toCharArray ( ) ; do { int dif = 0 ; for ( int i = 0 ; i < n ; i ++ ) { if ( s . charAt ( i ) != dup [ i % 3 ] ) { dif ++ ; } } mini = Math . min ( mini , dif ) ; } while ( next_permutation ( dup ) ) ; return mini ; } static boolean next_permutation ( char [ ] p ) { for ( int a = p . length - 2 ; a >= 0 ; -- a ) { if ( p [ a ] < p [ a + 1 ] ) { for ( int b = p . length - 1 ; ; -- b ) { if ( p [ b ] > p [ a ] ) { char t = p [ a ] ; p [ a ] = p [ b ] ; p [ b ] = t ; for ( ++ a , b = p . length - 1 ; a < b ; ++ a , -- b ) { t = p [ a ] ; p [ a ] = p [ b ] ; p [ b ] = t ; } return true ; } } } } return false ; } public static void main ( String args [ ] ) { String s = "2101200" ; System . out . println ( countMinimalReplacements ( s ) ) ; } }