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

0 0 6 minutes read

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++

// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
 
// Function to find minimum Hamming
// Distance after atmost one operation
int minimumHammingDistance(string S, int K)
{
    // Store the size of the string
    int n = S.size();
 
    // Store the prefix sum of 1s
    int pref[n];
 
    // Create Prefix Sum array
    pref[0] = S[0] - '0';
    for (int i = 1; i < n; i++)
        pref[i] = pref[i - 1] + (S[i] - '0');
 
    // Initialize cnt as number of ones
    // in string S
    int cnt = pref[n - 1];
 
    // Store the required result
    int ans = cnt;
 
    // Traverse the string, S
    for (int i = 0; i < n - K; i++) {
 
        // Store the number of 1s in the
        // substring S[i, i+K-1]
        int value = pref[i + K - 1]
                    - (i - 1 >= 0 ? pref[i - 1] : 0);
 
        // Update the answer
        ans = min(ans, cnt - value + (K - value));
    }
 
    // Return the result
    return ans;
}
 
// Driver Code
int main()
{
 
    // Given Input
    string s = "101";
    int K = 2;
 
    // Function Call
    cout << minimumHammingDistance(s, K);
 
    return 0;
}

Java

// Java program for the above approach
public class GFG 
{
 
// Function to find minimum Hamming
// Distance after atmost one operation
static int minimumHammingDistance(String S, int K)
{
   
    // Store the size of the string
    int n = S.length();
 
    // Store the prefix sum of 1s
    int []pref =  new int [n];
 
    // Create Prefix Sum array
    pref[0] = S.charAt(0) - '0';
    for (int i = 1; i < n; i++)
        pref[i] = pref[i - 1] + (S.charAt(i) - '0');
 
    // Initialize cnt as number of ones
    // in string S
    int cnt = pref[n - 1];
 
    // Store the required result
    int ans = cnt;
 
    // Traverse the string, S
    for (int i = 0; i < n - K; i++) {
 
        // Store the number of 1s in the
        // substring S[i, i+K-1]
        int value = pref[i + K - 1] - (i - 1 >= 0 ? pref[i - 1] : 0);
 
        // Update the answer
        ans = Math.min(ans, cnt - value + (K - value));
    }
 
    // Return the result
    return ans;
}
 
// Driver Code
public static void main(String args[])
{
    // Given Input
    String s = "101";
    int K = 2;
 
    // Function Call
    System.out.println(minimumHammingDistance(s, K));
    }
}
 
// This code is contributed by SoumikMondal

Python3

# Py program for the above approach
 
# Function to find minimum Hamming
# Distance after atmost one operation
def minimumHammingDistance(S, K):
    # Store the size of the string
    n = len(S)
 
    # Store the prefix sum of 1s
    pref = [0] * n
 
    # Create Prefix Sum array
    pref[0] = ord(S[0]) - ord('0')
    for i in range(1,n):
        pref[i] = pref[i - 1] + (ord(S[i]) - ord('0'))
 
    # Initialize cnt as number of ones
    # in string S
    cnt = pref[n - 1]
 
    # Store the required result
    ans = cnt
 
    # Traverse the string, S
    for i in range(n - K):
       
        # Store the number of 1s in the
        # substring S[i, i+K-1]
        value = pref[i + K - 1] - (pref[i-1] if (i - 1) >= 0 else 0)
 
        # Update the answer
        ans = min(ans, cnt - value + (K - value))
 
    # Return the result
    return ans
 
# Driver Code
if __name__ == '__main__':
 
    # Given Input
    s = "101"
    K = 2
 
    # Function Call
    print (minimumHammingDistance(s, K))
 
# This code is contributed by mohit kumar 29.

C#

// C# program for the above approach
using System;
using System.Collections.Generic;
 
class GFG 
{
 
// Function to find minimum Hamming
// Distance after atmost one operation
static int minimumHammingDistance(string S, int K)
{
   
    // Store the size of the string
    int n = S.Length;
 
    // Store the prefix sum of 1s
    int []pref =  new int [n];
 
    // Create Prefix Sum array
    pref[0] = (int)S[0] - 48;
    for (int i = 1; i < n; i++)
        pref[i] = pref[i - 1] + ((int)S[i] - 48);
 
    // Initialize cnt as number of ones
    // in string S
    int cnt = pref[n - 1];
 
    // Store the required result
    int ans = cnt;
 
    // Traverse the string, S
    for (int i = 0; i < n - K; i++) {
 
        // Store the number of 1s in the
        // substring S[i, i+K-1]
        int value = pref[i + K - 1] - (i - 1 >= 0 ? pref[i - 1] : 0);
 
        // Update the answer
        ans = Math.Min(ans, cnt - value + (K - value));
    }
 
    // Return the result
    return ans;
}
 
// Driver Code
public static void Main()
{
    // Given Input
    string s = "101";
    int K = 2;
 
    // Function Call
     Console.Write(minimumHammingDistance(s, K));
    }
}
 
// This code is contributed by SURENDRA_GANGWAR.

Javascript

<script>
   
// JavaScript program for the above approach
 
// Function to find minimum Hamming
// Distance after atmost one operation
function minimumHammingDistance(S, K)
{
   
    // Store the size of the string
    let n = S.length;
 
    // Store the prefix sum of 1s
    let pref =  new Array(n);
 
    // Create Prefix Sum array
    pref[0] = S[0] - '0';
    for (let i = 1; i < n; i++)
        pref[i] = pref[i - 1] + (S[i] - '0');
 
    // Initialize cnt as number of ones
    // in string S
    let cnt = pref[n - 1];
 
    // Store the required result
    let ans = cnt;
 
    // Traverse the string, S
    for (let i = 0; i < n - K; i++) {
 
        // Store the number of 1s in the
        // substring S[i, i+K-1]
        let value = pref[i + K - 1] - (i - 1 >= 0 ? pref[i - 1] : 0);
 
        // Update the answer
        ans = Math.min(ans, cnt - value + (K - value));
    }
 
    // Return the result
    return ans;
}
 
// Driver Code
 
    // Given Input
    let s = "101";
    let K = 2;
 
    // Function Call
    document.write(minimumHammingDistance(s, K));
         
</script>

Output

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

Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 zambiatek!