Minimize swaps of pairs of characters required such that no two adjacent characters in the string are same | Java program for the above approach ; Function to check if S contains any pair of adjacent characters that are same ; Traverse the String S ; If current pair of adjacent characters are the same ; Return true ; Utility function to find the minimum number of swaps of pair of characters required to make all pairs of adjacent characters different ; Check if the required String is formed already ; Traverse the String S ; Swap the characters at i and j position ; Swap for Backtracking Step ; Function to find the minimum number of swaps of pair of characters required to make all pairs of adjacent characters different ; Stores the resultant minimum number of swaps required ; Function call to find the minimum swaps required ; Print the result ; Driver Code
import java . util . * ; class GFG { static int ansSwaps ; static boolean check ( char [ ] S ) { for ( int i = 1 ; i < S . length ; i ++ ) { if ( S [ i - 1 ] == S [ i ] ) { return false ; } } return true ; } static void minimumSwaps ( char [ ] S , int swaps , int idx ) { if ( check ( S ) ) { ansSwaps = Math . min ( ansSwaps , swaps ) ; } for ( int i = idx ; i < S . length ; i ++ ) { for ( int j = i + 1 ; j < S . length ; j ++ ) { swap ( S , i , j ) ; minimumSwaps ( S , swaps + 1 , i + 1 ) ; S = swap ( S , i , j ) ; } } } static char [ ] swap ( char [ ] arr , int i , int j ) { char temp = arr [ i ] ; arr [ i ] = arr [ j ] ; arr [ j ] = temp ; return arr ; } static void findMinimumSwaps ( char [ ] S ) { ansSwaps = Integer . MAX_VALUE ; minimumSwaps ( S , 0 , 0 ) ; if ( ansSwaps == Integer . MAX_VALUE ) System . out . print ( " - 1" ) ; else System . out . print ( ansSwaps ) ; } public static void main ( String [ ] args ) { String S = " ABAACD " ; findMinimumSwaps ( S . toCharArray ( ) ) ; } }