Minimum number of swaps required such that a given substring consists of exactly K 1 s | CPP program for the above approach ; 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
#include <bits/stdc++.h> NEW_LINE using namespace std ; int minimumSwaps ( string s , int l , int r , int k ) { int n = s . length ( ) ; int tot_ones = 0 , tot_zeros = 0 ; for ( int i = 0 ; i < s . length ( ) ; i ++ ) { if ( s [ i ] == '1' ) tot_ones ++ ; else tot_zeros ++ ; } int ones = 0 , zeros = 0 , sum = 0 ; for ( int i = l - 1 ; i < r ; i ++ ) { if ( s [ i ] == '1' ) { ones ++ ; sum ++ ; } else zeros ++ ; } int rem_ones = tot_ones - ones ; int rem_zeros = tot_zeros - zeros ; if ( k >= sum ) { int rem = k - sum ; if ( zeros >= rem && rem_ones >= rem ) return rem ; } else if ( k < sum ) { int rem = sum - k ; if ( ones >= rem && rem_zeros >= rem ) return rem ; } return -1 ; } int main ( ) { string S = "110011111000101" ; int L = 5 , R = 8 , K = 2 ; cout << minimumSwaps ( S , L , R , K ) ; }