Minimice la distancia de hamming en la string binaria configurando solo bits de substring de tamaño K

Dadas dos strings binarias S y T de longitud N y un entero positivo K . Inicialmente, todos los caracteres de T son ‘0’ . La tarea es encontrar la distancia mínima de Hamming después de elegir una substring de tamaño K y hacer que todos los elementos de la string T sean ‘1’ solo una vez.

Ejemplos:

Entrada: S = «101», K = 2
Salida: 1
Explicación: Inicialmente, la string T = «000», una forma posible es cambiar todos los 0 en el rango [0, 1] a 1. Por lo tanto, la string T se convierte en «110» y la distancia de hamming entre S y T es 2, que es la mínima posible.

Entrada: S = “1100”, K=3
Salida: 1

Enfoque ingenuo: el enfoque más simple es considerar cada substring de tamaño K y hacer que todos los elementos sean 1 y luego verificar la distancia de hamming con la string, S . Después de verificar todas las substrings, imprima la distancia mínima de hamming.

Complejidad temporal: O(N×K)
Espacio auxiliar: O(1)

Enfoque: este problema se puede resolver creando una suma de array de prefijos que almacena la suma de prefijos del recuento de unos en la string S . Siga los pasos a continuación para resolver el problema:

• Cree una array de suma de prefijos pref[] de la string S inicializando pref[0] como 0 actualizando pref[i] como pref[i-1] +(S[i] – ‘0’) para cada índice i .
• Almacene el recuento total de unos en la string, S en una variable cnt .
• Inicialice una variable ans como cnt para almacenar el resultado requerido.
• Iterar en el rango [0, NK] usando la variable i
  • Inicialice una variable val como pref[i+K-1] – pref[i-1] para almacenar el recuento de unos en la substring S[i, i+K-1] .
  • Cree dos variables A y B para almacenar la distancia de hamming fuera de la substring actual y la distancia de hamming dentro de la substring actual e inicialice A con cnt – K y B con K – val .
  • Actualice el valor de ans con el mínimo de ans y (A + B) .
• Imprime el valor de ans como resultado.

A continuación se muestra la implementación del enfoque anterior:

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

# 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# 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.

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

2

Complejidad temporal: O(N)
Espacio auxiliar: O(N)