Minimize the Hamming distance of a binary string by setting a substring containing only K bits

The Hamming distance between two strings of equal length is the number of all positions where different values ​​exist at the corresponding positions. We can understand through the following example:

S= “ramanisgoing”

S= “ramanisgoing”

T=“dishaisgoing”

Here, 5 is the Hamming distance between the two strings S and T, since raman and disha are two words that make the difference in the strings equal.

Problem Statement

However, in this problem, we need to find the Hamming distance between two strings containing only binary digits. One string will be provided by the user, let's say S, and another string, let's say T. Initially, we assume it contains only '0' bits and is equal to the size of the given string. We will get a number 'k' whose value represents the number of elements a substring can consist of only '1's as its elements so that we place that substring of size k in the string(T) Any position that minimizes the Hamming distance between two substrings S and T.

Let's try to understand this problem through some examples.

Input − S = "100111" K = 5

Output - 3

Explanation − The initial string T is equal to "000000", and the string T will be changed to compare with the string S to find the minimum Hamming distance when k=5, as shown below : "111110" and "011111".

The Hamming distance between 100111 and 000000 is 4. The Hamming distance between 100111 and 111110 is 3, and the Hamming distance between 100111 and 011111 is also 3.

But the minimum Hamming distance will be 3, because 3 is less than 4. Therefore, our answer is 3.

- S = "100101" K = 5

- 3

− As the initial string T will be equal to "000000", and the string T will be changed to compare with the string S to find the minimum Hamming distance when k=5, as follows Display: "111110" and "011111".

The Hamming distance between 100101 and 000000 is 3. The Hamming distance between 100101 and 111110 is 4, and the Hamming distance between 100101 and 011111 is also 4.

But the minimum Hamming distance will be 3, because 3 is less than 4. Therefore, our answer is 3.

Explanation of the problem

Let's try to understand this problem and find a solution.

Solution 1 Brutal solution

We will modify the string T by changing the positions of substrings with different initial and end points in order to obtain the smallest Hamming distance among all possible strings.

Example

The following is the C program implementation of the above method:

#include <bits/stdc++.h>
using namespace std;
// Make a function to get minimum hamming distance through iteration
int helper(string S,int k){
   // n is the size of the string
   int n=S.size();
   // Take another string T and initiate it with zero bits size equal to that of S
   string T;
   for(int i=0;i<n;i++){
      T+="0";
   }
   // Take another string v to initiate it same as T
   string v=T;
   // Define mini as the hamming distance between T and S
   int mini=0;
   int l=0; 
   while(l<n){
      if(S[l]!=T[l])mini++;
         l++;
   }
   for(int i=0;i<n-k+1;i++){
      int j=0,a=0,l=0;
      // alter string v by changing bits of size k
      while(j<k){
          v[j+i]='1';
          j++;
      }
      // calculate hamming distance
      while(l<n){
         if(S[l]!=v[l])a++;
           l++;
      }
      // Check if the previous hamming distance is greater than the current hamming distance, if yes then replace that distance element
      if(mini>a){
         mini=a;
      }
      // Again assign v as the T string
      v=T;
    }
    // return the minimum hamming distance found through the above iterations
    return mini;
}
int main() {
   // Give input string S
   string S = "100101";
   // Give the value of k that is the substring size
   int K = 5;
   // Call the helper function
   cout << "The minimum hamming distance is: "<< helper(S,K);
   return 0;
}

Output

The minimum hamming distance is: 3

Solution 2 Optimization plan

algorithm

• Use the prefix sum array to calculate the number of 1's and store it as our minimum Hamming distance

• Traverse the string S to find the values ​​between K different substrings in the string S.

• If (i-1<0), then use the value v as arr[i K-1], otherwise use the value v as (arr[i K-1]-arr[i-1])

• Store the minimum value by finding the minimum value between the previous Hamming distance and the current Hamming distance.

• The current Hamming distance can be found by operating on the number of zero elements in the (K - v) substring and the number of zeros in the current S substring

• Finally, return the overall minimum distance.

Example

The following is the C program implementation of the above method

#include <bits/stdc++.h>
using namespace std;
// Make a helper function to get minimum hamming distance through iteration
int helper(string S, int K){
 // n is the size of the string
	int n = S.size();
	// initialize an array of size 'n'
	int arr[n];
	if(S[0]=='0')arr[0]=0;
	else arr[0]=1;
	// Count the number of 1's in the string S
	for (int i = 1; i < n; i++){
	    if(S[i]=='0')arr[i]=arr[i-1];
	    else arr[i]=arr[i-1]+1;
	}
	int cnt = arr[n - 1];	
	// Define mini as the hamming distance between T and S
	int mini = cnt;
	// Traverse through S to find the minimum
	for (int i = 0; i < n - K; i++) {
		int v;
		if(i-1==-1)v=arr[i+K-1];
		else v= arr[i+K-1]-arr[i-1];
		// Store the minimum
		mini = min(mini, cnt - v + (K - v));
	}
    // Return the minimum hamming distance
	return mini;
}
int main(){
	// Give input string S
    string S = "100101";
    // Give the value of k that is the substring size
    int K = 5;
    // Call the helper function
    cout << "The minimum hamming distance is: "<< helper(S,K);
    return 0;
}

Output

The minimum hamming distance is: 3

in conclusion

In this article, to find the minimum Hamming distance, we will first see a simple method, but to improve its time complexity, we will use the concept of prefix and array, through which we can to avoid double counting.

The above is the detailed content of Minimize the Hamming distance of a binary string by setting a substring containing only K bits. For more information, please follow other related articles on the PHP Chinese website!