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
using System ; using System . Collections . Generic ; class GFG { static bool sameJavaharAdj ( char [ ] str ) { int n = str . Length , i ; HashSet < char > st = new HashSet < char > ( ) ; st . Add ( str [ 0 ] ) ; for ( i = 1 ; i < n ; i ++ ) { if ( str [ i ] == str [ i - 1 ] ) { continue ; } if ( st . Contains ( str [ i ] ) & ! st . Equals ( str [ i ] ) ) { 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 int . MaxValue ; } } 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 str = " abbaacb " ; int n = str . Length , cnt = 0 , minm = int . MaxValue ; Console . WriteLine ( minSwaps ( str . ToCharArray ( ) , 0 , n - 1 , cnt , minm ) ) ; ; } }