Maximize sum of assigned weights by flipping at most K bits in given Binary String | 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
def findMax ( s , n , k ) : NEW_LINE INDENT ans = 0 ; NEW_LINE l = 0 ; NEW_LINE ind = - 1 ; NEW_LINE indf = - 1 ; NEW_LINE ls = set ( [ ] ) NEW_LINE for i in range ( n ) : NEW_LINE INDENT if ( s [ i ] == '0' ) : NEW_LINE INDENT l += 1 NEW_LINE DEDENT elif ( s [ i ] == '1' and l > 0 and ans != 0 ) : NEW_LINE INDENT ls . add ( l ) ; NEW_LINE l = 0 ; NEW_LINE DEDENT if ( s [ i ] == '1' ) : NEW_LINE INDENT ind = i ; NEW_LINE l = 0 ; NEW_LINE if ( indf == - 1 ) : NEW_LINE INDENT indf = i ; NEW_LINE DEDENT if ( i > 0 and s [ i - 1 ] == '1' ) : NEW_LINE INDENT ans += 2 ; NEW_LINE DEDENT else : NEW_LINE INDENT ans += 1 ; NEW_LINE DEDENT DEDENT DEDENT curr = 0 NEW_LINE while ( k > 0 and len ( ls ) != 0 ) : NEW_LINE INDENT for i in ls : NEW_LINE curr = i NEW_LINE break NEW_LINE if ( k >= curr ) : NEW_LINE INDENT ans += ( 2 * curr + 1 ) ; NEW_LINE k -= curr ; NEW_LINE DEDENT else : NEW_LINE INDENT ans += ( 2 * k ) ; NEW_LINE k = 0 ; NEW_LINE DEDENT ls . remove ( curr ) ; NEW_LINE DEDENT if ( k > 0 ) : NEW_LINE INDENT ans += ( 2 * min ( k , n - ( ind + 1 ) ) - 1 ) ; NEW_LINE k -= min ( k , n - ( ind + 1 ) ) ; NEW_LINE if ( ind > - 1 ) : NEW_LINE INDENT ans += 1 NEW_LINE DEDENT DEDENT if ( k > 0 ) : NEW_LINE INDENT ans += ( min ( indf , k ) * 2 - 1 ) ; NEW_LINE if ( indf > - 1 ) : NEW_LINE INDENT ans += 1 NEW_LINE DEDENT DEDENT return ans NEW_LINE DEDENT if __name__ == " _ _ main _ _ " : NEW_LINE INDENT s = "1110000101" ; NEW_LINE N = len ( s ) NEW_LINE K = 3 ; NEW_LINE print ( findMax ( s , N , K ) ) ; NEW_LINE DEDENT