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 operationint 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 Codeint main(){ // Given Input string s = "101"; int K = 2; // Function Call cout << minimumHammingDistance(s, K); return 0;} |
Java
// Java program for the above approachpublic class GFG {// Function to find minimum Hamming// Distance after atmost one operationstatic 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 Codepublic 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 operationdef 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 Codeif __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 approachusing System;using System.Collections.Generic;class GFG {// Function to find minimum Hamming// Distance after atmost one operationstatic 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 Codepublic 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 operationfunction 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
2
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 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!