Número mínimo de pasos necesarios para eliminar la substring K de la string dada

Dada una string binaria S y una substring K , la tarea es encontrar el número mínimo de pasos necesarios para cambiar los caracteres en una string binaria de modo que no contenga la substring K dada . Nota: En un solo paso podemos cambiar de 0 a 1 o viceversa.
Ejemplos: 

Entrada: S = «0111011», K = «011» 
Salida: 2 
Explicación: 
En la string anterior tenemos la substring 011 2 veces, por lo tanto, cambie el bit 3 y el bit 7.

Entrada: S = «010010», K = «0100» 
Salida: 1 
Explicación: 
En la string anterior tenemos la substring 0100 por 1 vez, cambie el cuarto bit de la string a 1. 

Enfoque ingenuo: El enfoque ingenuo es utilizar la búsqueda de patrones . Iterar a través de la string para N! veces (N = longitud de la string binaria). En cada iteración, verifique la substring K y, si coincide, incremente el conteo. Por último, imprima el recuento, que será el número de pasos necesarios para hacer que la string no contenga la substring K dada .

Complejidad de tiempo: O(M*N) donde M es la longitud de la substring y N es la longitud de la string binaria. 
Espacio Auxiliar: O(1)

Enfoque eficiente: para optimizar el método anterior, la idea es reemplazar la substring con una string vacía y restar la longitud de la string resultante de la longitud de la string original. Después de esto, divida la string resultante con la longitud de la substring K dada para obtener el número mínimo de pasos necesarios para cambiar los caracteres de la string S dada para que no contenga la substring K dada .

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

// C++ program for the above approach
#include<bits/stdc++.h>
#include <boost/algorithm/string/replace.hpp>
using namespace std;
 
// Function that counts the total
// number of character to be flipped
// such the string b doesn't contains
// string sub as a substring
int flipCharacters(string b,
                   string sub)
{
     
    // Replacing the substring with ""
    // and find the difference between
    // the length of the resultant
    // string and the original
    // string length
    int res = b.size();
    boost::replace_all(b, sub, "");
    res = res - b.size();
              
    // Divide the result
    // with substring length
    int temp = res / sub.size();
 
    // Return the final count
    return temp;
}
 
// Driver Code
int main()
{
     
    // Given string S and substring K
    string S = "010010";
    string K = "0100";
 
    // Function call
    int result = flipCharacters(S, K);
 
    // Print the minimum flip
    cout << (result);
}
 
// This code is contributed by Amit Katiyar

// Java program for the above approach
import java.util.*;
 
public class Test {
 
    // Function that counts the total
    // number of character to be flipped
    // such the string b doesn't contains
    // string sub as a substring
    static int flipCharacters(String b,
                              String sub)
    {
 
        // Replacing the substring with ""
        // and find the difference between
        // the length of the resultant
        // string and the original
        // string length
 
        int res = b.length()
                  - b.replaceAll(sub, "")
                        .length();
 
        // Divide the result
        // with substring length
 
        int temp = res / sub.length();
 
        // Return the final count
        return temp;
    }
 
    // Driver Code
    public static void main(String[] args)
    {
 
        // Given string S and substring K
        String S = "010010";
        String K = "0100";
 
        // Function Call
        int result = flipCharacters(S, K);
 
        // Print the minimum flip
        System.out.println(result);
    }
}

# Python3 program for the above approach
def flipCharacters(b, sub):
     
    # Replace the substring with
    # "" (emptryString)
    b1 = b.replace(sub, "")
     
    n = int((len(b)-len(b1))/len(sub))
     
    return n
 
# Driver Code
if __name__ == '__main__':
 
# Given string S and substring K
    S ="010010"
    X ="0100"
 
# Function Call
    result = flipCharacters(S, X)
 
# Print the minimum flip
    print(result)

// C# program for the above approach
using System;
class GFG
{
  
  // Function that counts the total
  // number of character to be flipped
  // such the string b doesn't contains
  // string sub as a substring
  static int flipCharacters(string b,
                            string sub)
  {
 
    // Replacing the substring with ""
    // and find the difference between
    // the length of the resultant
    // string and the original
    // string length
 
    int res = b.Length -
              b.Replace(sub, "").Length;
 
    // Divide the result
    // with substring length
    int temp = res / sub.Length;
 
    // Return the final count
    return temp;
  }
 
  // Driver Code
  public static void Main(string[] args)
  {
 
    // Given string S and substring K
    string S = "010010";
    string K = "0100";
 
    // Function Call
    int result = flipCharacters(S, K);
 
    // Print the minimum flip
    Console.Write(result);
  }
}
 
// This code is contributed by rutvik_56

<script>
 
// JavaScript program for the above approach
 
// Function that counts the total
// number of character to be flipped
// such the string b doesn't contains
// string sub as a substring
function flipCharacters(b, sub)
{
     
    // Replacing the substring with ""
    // and find the difference between
    // the length of the resultant
    // string and the original
    // string length
    var res = b.length - b.replace(sub, "").length;
              
    // Divide the result
    // with substring length
    var temp = parseInt(res / sub.length);
 
    // Return the final count
    return temp;
}
 
// Driver Code
 
// Given string S and substring K
var S = "010010";
var K = "0100";
 
// Function call
var result = flipCharacters(S, K);
 
// Print the minimum flip
document.write(result);
 
 
</script>

1

Complejidad de tiempo: O(N) , donde N es la longitud de la string. 
Espacio Auxiliar: O(1)