Maximize sum of assigned weights by flipping at most K bits in given Binary String | C ++ program of the above approach ; Function to find maximum sum of weights of binary string after at most K flips ; Stores lengths of substrings of the form 1. . 00. . 1 s ; Stores the index of last 1 encountered in the string ; Stores the index of first 1 encountered ; Stores lengths of all substrings having of 0 s enclosed by 1 s at both ends ; Traverse the string ; If character is 0 ; If character is 1 First Priority ; Second Priority ; Add according to the first priority ; Stores length of the shortest substring of 0 s ; Convert shortest substrings of 0 s to 1 s ; Add according to the first priority ; Add according to the third priority ; If more 0 s can be made into 1 , then check for 0 s at ends ; Update the ans ; If K is non - zero , then flip 0 s at the beginning ; Return the final weights ; Driver Code ; Given string str ; Given K flips ; Function Call
#include <bits/stdc++.h> NEW_LINE using namespace std ; int findMax ( string s , int n , int k ) { int ans = 0 ; int l = 0 ; int ind = -1 ; int indf = -1 ; multiset < int > ls ; for ( int i = 0 ; i < n ; i ++ ) { if ( s [ i ] == '0' ) l ++ ; else if ( s [ i ] == '1' && l > 0 && ans != 0 ) { ls . insert ( l ) ; l = 0 ; } if ( s [ i ] == '1' ) { ind = i ; l = 0 ; if ( indf == -1 ) indf = i ; if ( i > 0 && s [ i - 1 ] == '1' ) ans += 2 ; else ans += 1 ; } } int curr ; while ( k > 0 && ! ls . empty ( ) ) { curr = * ls . begin ( ) ; if ( k >= curr ) { ans += ( 2 * curr + 1 ) ; k -= curr ; } else { ans += ( 2 * k ) ; k = 0 ; } ls . erase ( ls . begin ( ) ) ; } if ( k > 0 ) { ans += ( 2 * min ( k , n - ( ind + 1 ) ) - 1 ) ; k -= min ( k , n - ( ind + 1 ) ) ; if ( ind > -1 ) ans ++ ; } if ( k > 0 ) { ans += ( min ( indf , k ) * 2 - 1 ) ; if ( indf > -1 ) ans ++ ; } return ans ; } int main ( ) { string str = "1110000101" ; int N = str . length ( ) ; int K = 3 ; cout << findMax ( str , N , K ) ; return 0 ; }