Minimum swaps to group similar characters side by side ? | checks whether a String has similar characters side by side ; If similar chars side by side , continue ; If we have found a char equal to current char and does not exist side to it , return false ; counts min swap operations to convert a String that has similar characters side by side ; Base case ; considering swapping of i and l chars ; Backtrack ; not considering swapping of i and l chars ; taking Math . min of above two ; Utility swap ; Driver code
import java . util . * ; class GFG { static boolean sameJavaharAdj ( char str [ ] ) { int n = str . length , i ; TreeSet < Character > st = new TreeSet < > ( ) ; st . add ( str [ 0 ] ) ; for ( i = 1 ; i < n ; i ++ ) { if ( str [ i ] == str [ i - 1 ] ) { continue ; } if ( st . contains ( str [ i ] ) & ( str [ i ] != st . last ( ) ) ) { return false ; } st . add ( str [ i ] ) ; } return true ; } static int minSwaps ( char str [ ] , int l , int r , int cnt , int minm ) { if ( l == r ) { if ( sameJavaharAdj ( str ) ) { return cnt ; } else { return Integer . MAX_VALUE ; } } for ( int i = l + 1 ; i <= r ; i ++ ) { swap ( str , i , l ) ; cnt ++ ; int x = minSwaps ( str , l + 1 , r , cnt , minm ) ; swap ( str , i , l ) ; cnt -- ; int y = minSwaps ( str , l + 1 , r , cnt , minm ) ; minm = Math . min ( minm , Math . min ( x , y ) ) ; } return minm ; } static void swap ( char [ ] arr , int i , int j ) { char temp = arr [ i ] ; arr [ i ] = arr [ j ] ; arr [ j ] = temp ; } public static void main ( String [ ] args ) { String str = " abbaacb " ; int n = str . length ( ) , cnt = 0 , minm = Integer . MAX_VALUE ; System . out . print ( minSwaps ( str . toCharArray ( ) , 0 , n - 1 , cnt , minm ) ) ; ; } }