Minimum number of swaps required such that a given substring consists of exactly K 1 s | Function to find the minimum number of swaps required such that the substring { s [ l ] , . . , s [ r ] } consists of exactly k 1 s ; Store the size of the string ; Store the total number of 1 s and 0 s in the entire string ; Traverse the string S to find the frequency of 1 and 0 ; Store the number of 1 s and 0 s in the substring s [ l , r ] ; Traverse the substring S [ l , r ] to find the frequency of 1 s and 0 s in it ; Store the count of 1 s and 0 s outside substring s [ l , r ] ; Check if the sum of the substring is at most K ; Store number of 1 s required ; Check if there are enough 1 s remaining to be swapped ; If the count of 1 s in the substring exceeds k ; Store the number of 0 s required ; Check if there are enough 0 s remaining to be swapped ; In all other cases , print - 1 ; Driver Code
def minimumSwaps ( s , l , r , k ) : NEW_LINE INDENT n = len ( s ) NEW_LINE tot_ones , tot_zeros = 0 , 0 NEW_LINE for i in range ( 0 , len ( s ) ) : NEW_LINE INDENT if ( s [ i ] == '1' ) : NEW_LINE INDENT tot_ones += 1 NEW_LINE DEDENT else : NEW_LINE INDENT tot_zeros += 1 NEW_LINE DEDENT DEDENT ones , zeros , Sum = 0 , 0 , 0 NEW_LINE for i in range ( l - 1 , r ) : NEW_LINE INDENT if ( s [ i ] == '1' ) : NEW_LINE INDENT ones += 1 NEW_LINE Sum += 1 NEW_LINE DEDENT else : NEW_LINE INDENT zeros += 1 NEW_LINE DEDENT DEDENT rem_ones = tot_ones - ones NEW_LINE rem_zeros = tot_zeros - zeros NEW_LINE if ( k >= Sum ) : NEW_LINE INDENT rem = k - Sum NEW_LINE if ( zeros >= rem and rem_ones >= rem ) : NEW_LINE INDENT return rem NEW_LINE DEDENT DEDENT elif ( k < Sum ) : NEW_LINE INDENT rem = Sum - k NEW_LINE if ( ones >= rem and rem_zeros >= rem ) : NEW_LINE INDENT return rem NEW_LINE DEDENT DEDENT return - 1 NEW_LINE DEDENT S = "110011111000101" NEW_LINE L , R , K = 5 , 8 , 2 NEW_LINE print ( minimumSwaps ( S , L , R , K ) ) NEW_LINE