Minimize hamming distance in Binary String by setting only one K size substring bits | Function to find minimum Hamming Distance after atmost one operation ; Store the size of the string ; Store the prefix sum of 1 s ; Create Prefix Sum array ; Initialize cnt as number of ones in string S ; Store the required result ; Traverse the string , S ; Store the number of 1 s in the substring S [ i , i + K - 1 ] ; Update the answer ; Return the result ; Driver Code ; Given Input ; Function Call
def minimumHammingDistance ( S , K ) : NEW_LINE INDENT n = len ( S ) NEW_LINE pref = [ 0 ] * n NEW_LINE pref [ 0 ] = ord ( S [ 0 ] ) - ord ( '0' ) NEW_LINE for i in range ( 1 , n ) : NEW_LINE INDENT pref [ i ] = pref [ i - 1 ] + ( ord ( S [ i ] ) - ord ( '0' ) ) NEW_LINE DEDENT cnt = pref [ n - 1 ] NEW_LINE ans = cnt NEW_LINE for i in range ( n - K ) : NEW_LINE INDENT value = pref [ i + K - 1 ] - ( pref [ i - 1 ] if ( i - 1 ) >= 0 else 0 ) NEW_LINE ans = min ( ans , cnt - value + ( K - value ) ) NEW_LINE DEDENT return ans NEW_LINE DEDENT if __name__ == ' _ _ main _ _ ' : NEW_LINE INDENT s = "101" NEW_LINE K = 2 NEW_LINE print ( minimumHammingDistance ( s , K ) ) NEW_LINE DEDENT