Cambios mínimos requeridos para hacer que la primera string sea una substring de la segunda string

Dadas dos strings S1 y S2 (tamaño de S1 <= tamaño de S2). La tarea es encontrar el número mínimo de caracteres que se reemplazarán en la string S2, de modo que la string S1 sea una substring de S2.
Ejemplos : 
 

Input : S1 = cdef, S2 = abbdef
Output : 1

Input : S1 = gfg, S2 = fgg
Output : 2 

Acercarse: 
 

1. Atraviesa la cuerda S2 
   • De cada índice en S2, verifique la cantidad de caracteres que no coinciden en la substring de longitud de S1
   • Almacene y actualice el mínimo de discrepancias anteriores y actuales en ans
2. Regresar respuesta

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

// CPP program to find the minimum number of
// characters to be replaced in string S2, such
// that S1 is a substring of S2
 
#include <bits/stdc++.h>
using namespace std;
 
// Function to find the minimum number of
// characters to be replaced in string S2, such
// that S1 is a substring of S2
int minimumChar(string S1, string S2)
{
    // Get the sizes of both strings
    int n = S1.size(), m = S2.size();
 
    int ans = INT_MAX;
 
    // Traverse the string S2
    for (int i = 0; i < m - n + 1; i++) {
        int minRemovedChar = 0;
 
        // From every index in S2, check the number of
        // mis-matching characters in substring of
        // length of S1
        for (int j = 0; j < n; j++) {
            if (S1[j] != S2[i + j]) {
                minRemovedChar++;
            }
        }
 
        // Take minimum of prev and current mis-match
        ans = min(minRemovedChar, ans);
    }
 
    // return answer
    return ans;
}
 
// Driver Code
int main()
{
    string S1 = "abc";
    string S2 = "paxzk";
 
    cout << minimumChar(S1, S2);
 
    return 0;
}

// C program to find the minimum number of
// characters to be replaced in string S2, such
// that S1 is a substring of S2
#include <stdio.h>
#include <string.h>
#include <limits.h>
 
int min(int a,int b)
{
  int min = a;
  if(min > b)
    min = b;
  return min;
}
 
// Function to find the minimum number of
// characters to be replaced in string S2, such
// that S1 is a substring of S2
int minimumChar(char S1[], char S2[])
{
    // Get the sizes of both strings
    int n = strlen(S1), m = strlen(S2);
 
    int ans = INT_MAX;
 
    // Traverse the string S2
    for (int i = 0; i < m - n + 1; i++) {
        int minRemovedChar = 0;
 
        // From every index in S2, check the number of
        // mis-matching characters in substring of
        // length of S1
        for (int j = 0; j < n; j++) {
            if (S1[j] != S2[i + j]) {
                minRemovedChar++;
            }
        }
 
        // Take minimum of prev and current mis-match
        ans = min(minRemovedChar, ans);
    }
 
    // return answer
    return ans;
}
 
// Driver Code
int main()
{
    char S1[] = "abc";
    char S2[] = "paxzk";
   
    printf("%d",minimumChar(S1, S2));
 
    return 0;
}
 
// This code is contributed by kothavvsaakash.

// Java program to find the minimum
// number of characters to be
// replaced in string S2, such
// that S1 is a substring of S2
import java.io.*;
 
class GFG
{
 
// Function to find the minimum
// number of characters to be
// replaced in string S2, such
// that S1 is a substring of S2
static int minimumChar(String S1,
                       String S2)
{
    // Get the sizes of both strings
    int n = S1.length();
    int m = S2.length();
 
    int ans = Integer.MAX_VALUE ;
 
    // Traverse the string S2
    for (int i = 0; i < m - n + 1; i++)
    {
        int minRemovedChar = 0;
 
        // From every index in S2, check
        // the number of mis-matching
        // characters in substring of
        // length of S1
        for (int j = 0; j < n; j++)
        {
            if (S1.charAt(j) != S2.charAt(i + j))
            {
                minRemovedChar++;
            }
        }
 
        // Take minimum of prev and
        // current mis-match
        ans = Math.min(minRemovedChar, ans);
    }
 
    // return answer
    return ans;
}
 
// Driver Code
public static void main (String[] args)
{
    String S1 = "abc";
    String S2 = "paxzk";
     
    System.out.println(minimumChar(S1, S2));
}
}
 
// This code is contributed by Shashank

# Python3 program to find the minimum
# number of characters to be replaced
# in string S2, such that S1 is a
# substring of S2
import sys
 
# Function to find the minimum number of
# characters to be replaced in string S2,
# such that S1 is a substring of S2
def minimumChar(S1, S2):
     
    # Get the sizes of both strings
    n, m = len(S1), len(S2)
 
    ans = sys.maxsize
 
    # Traverse the string S2
    for i in range(m - n + 1):
        minRemovedChar = 0
 
        # From every index in S2, check the
        # number of mis-matching characters
        # in substring of length of S1
        for j in range(n):
            if (S1[j] != S2[i + j]):
                minRemovedChar += 1
                 
        # Take minimum of prev and
        # current mis-match
        ans = min(minRemovedChar, ans)
         
    # return answer
    return ans
     
# Driver Code
if __name__ == '__main__':
    S1 = "abc"
    S2 = "paxzk"
    print(minimumChar(S1, S2))
 
# This code is contributed
# by PrinciRaj1992

// C# program to find the minimum
// number of characters to be
// replaced in string S2, such
// that S1 is a substring of S2
using System;
 
class GFG
{
 
// Function to find the minimum
// number of characters to be
// replaced in string S2, such
// that S1 is a substring of S2
static int minimumChar(String S1,
                       String S2)
{
    // Get the sizes of both strings
    int n = S1.Length;
    int m = S2.Length;
 
    int ans = Int32.MaxValue ;
 
    // Traverse the string S2
    for (int i = 0; i < m - n + 1; i++)
    {
        int minRemovedChar = 0;
 
        // From every index in S2, check
        // the number of mis-matching
        // characters in substring of
        // length of S1
        for (int j = 0; j < n; j++)
        {
            if (S1[j] != S2[i + j])
            {
                minRemovedChar++;
            }
        }
 
        // Take minimum of prev and
        // current mis-match
        ans = Math.Min(minRemovedChar, ans);
    }
 
    // return answer
    return ans;
}
 
// Driver Code
public static void Main()
{
    String S1 = "abc";
    String S2 = "paxzk";
     
    Console.WriteLine(minimumChar(S1, S2));
}
}
 
// This code is contributed
// by Akanksha Rai(Abby_akku)

<?php
// PHP program to find the minimum
// number of characters to be replaced
// in string S2, such that S1 is a
// substring of S2
 
// Function to find the minimum number
// of characters to be replaced in
// string S2, such that S1 is a
// substring of S2
function minimumChar($S1, $S2)
{
    // Get the sizes of both strings
    $n = strlen($S1);
    $m = strlen($S2);
 
    $ans = PHP_INT_MAX;
 
    // Traverse the string S2
    for ($i = 0; $i < $m - $n + 1; $i++)
    {
        $minRemovedChar = 0;
 
        // From every index in S2, check
        // the number of mis-matching
        // characters in substring of
        // length of S1
        for ($j = 0; $j < $n; $j++)
        {
            if ($S1[$j] != $S2[$i + $j])
            {
                $minRemovedChar++;
            }
        }
 
        // Take minimum of prev and
        // current mis-match
        $ans = min($minRemovedChar, $ans);
    }
 
    // return answer
    return $ans;
}
 
// Driver Code
$S1 = "abc";
$S2 = "paxzk";
 
echo minimumChar($S1, $S2);
 
// This code is contributed by ajit.
?>

<script>
    // Javascript program to find the minimum
    // number of characters to be
    // replaced in string S2, such
    // that S1 is a substring of S2
     
    // Function to find the minimum
    // number of characters to be
    // replaced in string S2, such
    // that S1 is a substring of S2
    function minimumChar(S1, S2)
    {
        // Get the sizes of both strings
        let n = S1.length;
        let m = S2.length;
 
        let ans = Number.MAX_VALUE;
 
        // Traverse the string S2
        for (let i = 0; i < m - n + 1; i++)
        {
            let minRemovedChar = 0;
 
            // From every index in S2, check
            // the number of mis-matching
            // characters in substring of
            // length of S1
            for (let j = 0; j < n; j++)
            {
                if (S1[j] != S2[i + j])
                {
                    minRemovedChar++;
                }
            }
 
            // Take minimum of prev and
            // current mis-match
            ans = Math.min(minRemovedChar, ans);
        }
 
        // return answer
        return ans;
    }
     
    let S1 = "abc";
    let S2 = "paxzk";
       
    document.write(minimumChar(S1, S2));
 
</script>

2

Complejidad de Tiempo : O(N * M).