Minimize hamming distance in Binary String by setting only one K size substring bits | Java 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
public class GFG { static int minimumHammingDistance ( String S , int K ) { int n = S . length ( ) ; int [ ] pref = new int [ n ] ; pref [ 0 ] = S . charAt ( 0 ) - '0' ; for ( int i = 1 ; i < n ; i ++ ) pref [ i ] = pref [ i - 1 ] + ( S . charAt ( 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 = Math . min ( ans , cnt - value + ( K - value ) ) ; } return ans ; } public static void main ( String args [ ] ) { String s = "101" ; int K = 2 ; System . out . println ( minimumHammingDistance ( s , K ) ) ; } }