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 min of above two ; Driver code
#include <bits/stdc++.h> NEW_LINE using namespace std ; bool sameCharAdj ( string str ) { int n = str . length ( ) , i ; set < char > st ; st . insert ( str [ 0 ] ) ; for ( i = 1 ; i < n ; i ++ ) { if ( str [ i ] == str [ i - 1 ] ) continue ; if ( st . find ( str [ i ] ) != st . end ( ) ) return false ; st . insert ( str [ i ] ) ; } return true ; } int minSwaps ( string str , int l , int r , int cnt , int minm ) { if ( l == r ) { if ( sameCharAdj ( str ) ) return cnt ; else return INT_MAX ; } for ( int i = l + 1 ; i <= r ; i ++ ) { swap ( str [ i ] , str [ l ] ) ; cnt ++ ; int x = minSwaps ( str , l + 1 , r , cnt , minm ) ; swap ( str [ i ] , str [ l ] ) ; cnt -- ; int y = minSwaps ( str , l + 1 , r , cnt , minm ) ; minm = min ( minm , min ( x , y ) ) ; } return minm ; } int main ( ) { string str = " abbaacb " ; int n = str . length ( ) , cnt = 0 , minm = INT_MAX ; cout << minSwaps ( str , 0 , n - 1 , cnt , minm ) << endl ; return 0 ; }