Minimum flips required in a binary string such that all K | Function to calculate and return the minimum number of flips to make string valid ; Stores the count of required flips ; Stores the last index of '1' in the string ; Check for the first substring of length K ; If i - th character is '1 ; If the substring had no '1 ; Increase the count of required flips ; Flip the last index of the window ; Update the last index which contains 1 ; Check for remaining substrings ; If last_idx does not belong to current window make it - 1 ; If the last character of the current substring is '1' , then update last_idx to i + k - 1 ; ; If last_idx == - 1 , then the current substring has no 1 ; Increase the count of flips ; Update the last index of the current window ; Store the last index of current window as the index of last '1' in the string ; Return the number of operations ; Driver Code
def minimumMoves ( S , K ) : NEW_LINE INDENT N = len ( S ) NEW_LINE ops = 0 NEW_LINE last_idx = - 1 NEW_LINE for i in range ( K ) : NEW_LINE DEDENT ' NEW_LINE INDENT if ( S [ i ] == '1' ) : NEW_LINE INDENT last_idx = i NEW_LINE DEDENT DEDENT ' NEW_LINE INDENT if ( last_idx == - 1 ) : NEW_LINE INDENT ops += 1 NEW_LINE S [ K - 1 ] = '1' NEW_LINE last_idx = K - 1 NEW_LINE DEDENT for i in range ( N - K + 1 ) : NEW_LINE INDENT if ( last_idx < i ) : NEW_LINE INDENT last_idx = - 1 NEW_LINE DEDENT if ( S [ i + K - 1 ] == '1' ) : NEW_LINE INDENT last_idx = i + K - 1 NEW_LINE DEDENT if ( last_idx == - 1 ) : NEW_LINE INDENT ops += 1 NEW_LINE S = S [ : i + K - 1 ] + '1' + S [ i + K : ] NEW_LINE last_idx = i + K - 1 NEW_LINE DEDENT DEDENT return ops NEW_LINE DEDENT S = "001010000" NEW_LINE K = 3 ; NEW_LINE print ( minimumMoves ( S , K ) ) NEW_LINE