Minimize hamming distance in Binary String by setting only one K size substring bits

Minimize hamming distance in Binary String by setting only one K size substring bits

Given two binary strings S and T of length N and a positive integer K. Initially, all characters of T are ‘0’. The task is to find the minimum Hamming distance after choosing a substring of size K and making all elements of string T as ‘1’ only once.

Examples:

Input: S = “101”, K = 2
Output: 1
Explanation: Initially string T = “000”, one possible way is to change all 0s in range [0, 1] to 1. Thus string T becomes “110” and the hamming distance between S and T is 2 which is the minimum possible.

Input: S = “1100”, K=3
Output: 1

Naive Approach: The simplest approach is to consider every substring of size K and make all the elements as 1 and then check the hamming distance with string, S. After checking all the substrings, print the minimum hamming distance.

Time Complexity: O(N×K)
Auxiliary Space: O(1)

Approach: This problem can be solved by creating a prefix array sum which stores the prefix sum of the count of ones in the string S. Follow the steps below to solve the problem:

• Create a prefix sum array pref[] of string S by initializing pref[0] as 0 updating pref[i] as pref[i-1] +(S[i] – ‘0’) for every index i.
• Store the total count of ones in the string, S in a variable cnt.
• Initialize a variable ans as cnt to store the required result.
• Iterate in the range [0, N-K] using the variable i
  • Initialize a variable val as pref[i+K-1] – pref[i-1] to store the count of ones in the substring S[i, i+K-1].
  • Create two variables A and B to store the hamming distance outside the current substring and the hamming distance inside the current substring and initialize A with cnt – K and B with K – val.
  • Update the value of ans with the minimum of ans and (A + B).
• Print the value of ans as the result.

Below is the implementation of the above approach:

C++

#include <bits/stdc++.h> 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; }

Time Complexity: O(N)
Auxiliary Space: O(N)

Attention reader! Don’t stop learning now. Get hold of all the important DSA concepts with the DSA Self Paced Course at a student-friendly price and become industry ready.  To complete your preparation from learning a language to DS Algo and many more,  please refer Complete Interview Preparation Course.

In case you wish to attend live classes with experts, please refer DSA Live Classes for Working Professionals and Competitive Programming Live for Students.

Adblock test (Why?)

Original page link

Best Cool Tech Gadgets

Top favorite technology gadgets