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
from sys import maxsize NEW_LINE def sameCharAdj ( string ) : NEW_LINE INDENT n = len ( string ) NEW_LINE st = set ( ) NEW_LINE st . add ( string [ 0 ] ) NEW_LINE for i in range ( 1 , n ) : NEW_LINE INDENT if string [ i ] == string [ i - 1 ] : NEW_LINE INDENT continue NEW_LINE DEDENT if string [ i ] in st : NEW_LINE INDENT return False NEW_LINE DEDENT st . add ( string [ i ] ) NEW_LINE DEDENT return True NEW_LINE DEDENT def minSwaps ( string , l , r , cnt , minm ) : NEW_LINE INDENT if l == r : NEW_LINE INDENT if sameCharAdj ( string ) : NEW_LINE INDENT return cnt NEW_LINE DEDENT else : NEW_LINE INDENT return maxsize NEW_LINE DEDENT DEDENT for i in range ( l + 1 , r + 1 , 1 ) : NEW_LINE INDENT string [ i ] , string [ l ] = string [ l ] , string [ i ] NEW_LINE cnt += 1 NEW_LINE x = minSwaps ( string , l + 1 , r , cnt , minm ) NEW_LINE string [ i ] , string [ l ] = string [ l ] , string [ i ] NEW_LINE cnt -= 1 NEW_LINE y = minSwaps ( string , l + 1 , r , cnt , minm ) NEW_LINE minm = min ( minm , min ( x , y ) ) NEW_LINE DEDENT return minm NEW_LINE DEDENT if __name__ == " _ _ main _ _ " : NEW_LINE INDENT string = " abbaacb " NEW_LINE string = list ( string ) NEW_LINE n = len ( string ) NEW_LINE cnt = 0 NEW_LINE minm = maxsize NEW_LINE print ( minSwaps ( string , 0 , n - 1 , cnt , minm ) ) NEW_LINE DEDENT