Minimum adjacent swaps required to make a binary string alternating | Function to find the minimum number of adjacent swaps to make the string alternating ; Count the no of zeros and ones ; Base Case ; Store no of min swaps when string starts with "1" ; Keep track of the odd positions ; Checking for when the string starts with "1" ; Adding the no of swaps to fix "1" at odd positions ; Store no of min swaps when string starts with "0" ; Keep track of the odd positions ; Checking for when the string starts with "0" ; Adding the no of swaps to fix "1" at odd positions ; Returning the answer based on the conditions when string length is even ; When string length is odd ; When no of ones is greater than no of zeros ; When no of ones is greater than no of zeros ; Driver Code
def minSwaps ( s ) : NEW_LINE INDENT ones = 0 NEW_LINE zeros = 0 NEW_LINE N = len ( s ) NEW_LINE for i in range ( N ) : NEW_LINE INDENT if s [ i ] == '1' : NEW_LINE INDENT ones += 1 NEW_LINE DEDENT else : NEW_LINE INDENT zeros += 1 NEW_LINE DEDENT DEDENT if ( ( N % 2 == 0 and ones != zeros ) or ( N % 2 == 1 and abs ( ones - zeros ) != 1 ) ) : NEW_LINE INDENT return - 1 NEW_LINE DEDENT ans_1 = 0 NEW_LINE j = 0 NEW_LINE for i in range ( N ) : NEW_LINE INDENT if ( s [ i ] == '1' ) : NEW_LINE INDENT ans_1 += abs ( j - i ) NEW_LINE j += 2 NEW_LINE DEDENT DEDENT ans_0 = 0 NEW_LINE k = 0 NEW_LINE for i in range ( N ) : NEW_LINE INDENT if ( s [ i ] == '0' ) : NEW_LINE INDENT ans_0 += abs ( k - i ) NEW_LINE k += 2 NEW_LINE DEDENT DEDENT if ( N % 2 == 0 ) : NEW_LINE INDENT return min ( ans_1 , ans_0 ) NEW_LINE DEDENT else : NEW_LINE INDENT if ( ones > zeros ) : NEW_LINE INDENT return ans_1 NEW_LINE DEDENT else : NEW_LINE INDENT return ans_0 NEW_LINE DEDENT DEDENT DEDENT if __name__ == ' _ _ main _ _ ' : NEW_LINE INDENT S = "110100" NEW_LINE print ( minSwaps ( S ) ) NEW_LINE DEDENT