Minimize hamming distance in Binary String by setting only one K size substring bits | C ++ program for the above approach ; 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
#include <bits/stdc++.h> NEW_LINE using namespace std ; int minimumHammingDistance ( string S , int K ) { int n = S . size ( ) ; int pref [ n ] ; pref [ 0 ] = S [ 0 ] - '0' ; for ( int i = 1 ; i < n ; i ++ ) pref [ i ] = pref [ i - 1 ] + ( S [ i ] - '0' ) ; int cnt = pref [ n - 1 ] ; int ans = cnt ; for ( int i = 0 ; i < n - K ; i ++ ) { int value = pref [ i + K - 1 ] - ( i - 1 >= 0 ? pref [ i - 1 ] : 0 ) ; ans = min ( ans , cnt - value + ( K - value ) ) ; } return ans ; } int main ( ) { string s = "101" ; int K = 2 ; cout << minimumHammingDistance ( s , K ) ; return 0 ; }