Minimize swaps of pairs of characters required such that no two adjacent characters in the string are same | Python3 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 ; Prvar the result ; Driver code
import sys NEW_LINE ansSwaps = 0 NEW_LINE def check ( S ) : NEW_LINE INDENT for i in range ( 1 , len ( S ) ) : NEW_LINE INDENT if ( S [ i - 1 ] == S [ i ] ) : NEW_LINE INDENT return False NEW_LINE DEDENT DEDENT return True NEW_LINE DEDENT def minimumSwaps ( S , swaps , idx ) : NEW_LINE INDENT global ansSwaps NEW_LINE if ( check ( S ) ) : NEW_LINE INDENT ansSwaps = 1 + min ( ansSwaps , swaps ) NEW_LINE DEDENT for i in range ( idx , len ( S ) ) : NEW_LINE INDENT for j in range ( i + 1 , len ( S ) ) : NEW_LINE INDENT swap ( S , i , j ) NEW_LINE minimumSwaps ( S , swaps + 1 , i + 1 ) NEW_LINE S = swap ( S , i , j ) NEW_LINE DEDENT DEDENT DEDENT def swap ( arr , i , j ) : NEW_LINE INDENT temp = arr [ i ] NEW_LINE arr [ i ] = arr [ j ] NEW_LINE arr [ j ] = temp NEW_LINE return arr NEW_LINE DEDENT def findMinimumSwaps ( S ) : NEW_LINE INDENT global ansSwaps NEW_LINE ansSwaps = sys . maxsize NEW_LINE minimumSwaps ( S , 0 , 0 ) NEW_LINE if ( ansSwaps == sys . maxsize ) : NEW_LINE INDENT print ( " - 1" ) NEW_LINE DEDENT else : NEW_LINE INDENT print ( ansSwaps ) NEW_LINE DEDENT DEDENT S = " ABAACD " NEW_LINE findMinimumSwaps ( S . split ( ) ) NEW_LINE