Caracteres mínimos que se reemplazarán para eliminar la substring dada

Dadas dos strings str1 y str2 . La tarea es encontrar el número mínimo de caracteres que se reemplazarán por $ en la string str1 de modo que str1 no contenga la string str2 como ninguna substring. 
Ejemplos: 
 

Input: str1 = "intellect", str2 = "tell"
Output: 1
4th character of string "str1" can be replaced by $
such that "int$llect" it does not contain "tell" 
as a substring.

Input: str1 = "google", str2 = "apple"
Output: 0

El enfoque es similar a la búsqueda de patrones | Juego 1 (búsqueda de patrones ingenuos)
La idea es encontrar la aparición más a la izquierda de la string ‘str2’ en la string ‘str1’. Si todos los caracteres de ‘str1’ coinciden con ‘str2’, reemplazaremos (o incrementaremos nuestra respuesta con uno) el último símbolo de ocurrencia e incrementaremos el índice de la string ‘str1’, de modo que verifique nuevamente la substring después de la carácter reemplazado (es decir, el índice i será igual a i + longitud (b) -1 ). 
A continuación se muestra la implementación del enfoque anterior: 
 

C++

// C++ implementation of above approach
#include <bits/stdc++.h>
using namespace std;
 
// function to calculate minimum
// characters to replace
int replace(string A, string B)
{
 
    int n = A.length(), m = B.length();
    int count = 0, i, j;
 
    for (i = 0; i < n; i++) {
        for (j = 0; j < m; j++) {
 
            // mismatch occurs
            if (A[i + j] != B[j])
                break;
        }
 
        // if all characters matched, i.e,
        // there is a substring of 'a' which
        // is same as string 'b'
        if (j == m) {
            count++;
 
             // increment i to index m-1 such that
            // minimum characters are replaced
            // in 'a'
            i += m - 1;
            
        }
    }
 
    return count;
}
 
// Driver Code
int main()
{
    string str1 = "aaaaaaaa";
    string str2 = "aaa";
 
    cout << replace(str1 , str2);
 
  return 0;
}

Java

// Java implementation of
// above approach
import java.io.*;
 
// function to calculate minimum
// characters to replace
class GFG
{
static int replace(String A, String B)
{
 
    int n = A.length(), m = B.length();
    int count = 0, i, j;
 
    for (i = 0; i < n; i++)
    {
        for (j = 0; j < m; j++)
        {
 
            // mismatch occurs
            if(i + j >= n)
            break;
            else if (A.charAt(i + j) != B.charAt(j))
                break;
        }
 
        // if all characters matched, i.e,
        // there is a substring of 'a' which
        // is same as string 'b'
        if (j == m)
        {
            count++;
 
            // increment i to index m-1 such that
            // minimum characters are replaced
            // in 'a'
            i += m - 1;
             
        }
    }
 
    return count;
}
 
// Driver Code
public static void main(String args[])
{
    String str1 = "aaaaaaaa";
    String str2 = "aaa";
 
    System.out.println(replace(str1 , str2));
}
}
 
// This code is contributed by Subhadeep

Python3

# Python3 implementation of the
# above approach
 
# Function to calculate minimum
# characters to replace
def replace(A, B):
 
    n, m = len(A), len(B)
    count, i = 0, 0
    while i < n:
         
        j = 0
        while j < m:
             
            # mismatch occurs
            if i + j >= n or A[i + j] != B[j]:
                break
             
            j += 1
             
        # If all characters matched, i.e,
        # there is a substring of 'a' which
        # is same as string 'b'
        if j == m:
            count += 1
                 
            # increment i to index m-1 such that
            # minimum characters are replaced
            # in 'a'
            i += m - 1
             
        i += 1
             
    return count
 
# Driver Code
if __name__ == "__main__":
 
    str1 = "aaaaaaaa"
    str2 = "aaa"
 
    print(replace(str1 , str2))
 
# This code is contributed by Rituraj Jain

C#

// C# implementation of above approach
using System;
 
// function to calculate minimum
// characters to replace
class GFG
{
public static int replace(string A,
                          string B)
{
 
    int n = A.Length, m = B.Length;
    int count = 0, i, j;
 
    for (i = 0; i < n; i++)
    {
        for (j = 0; j < m; j++)
        {
 
            // mismatch occurs
            if (i + j >= n)
            {
            break;
            }
            else if (A[i + j] != B[j])
            {
                break;
            }
        }
 
        // if all characters matched, i.e,
        // there is a substring of 'a'
        // which is same as string 'b'
        if (j == m)
        {
            count++;
 
            // increment i to index m-1
            // such that minimum characters
            // are replaced in 'a'
            i += m - 1;
 
        }
    }
 
    return count;
}
 
// Driver Code
public static void Main(string[] args)
{
    string str1 = "aaaaaaaa";
    string str2 = "aaa";
 
    Console.WriteLine(replace(str1, str2));
}
}
 
// This code is contributed
// by Shrikant13

PHP

<?php
// PHP implementation of above approach
 
// function to calculate minimum
// characters to replace
function replace($A, $B)
{
    $n = strlen($A);
    $m = strlen($B);
    $count = 0;
 
    for ($i = 0; $i < $n; $i++)
    {
        for ($j = 0; $j < $m; $j++)
        {
 
            // mismatch occurs
            if ($i + $j >= $n)
            {
                break;
            }
            else if ($A[$i + $j] != $B[$j])
            {
                break;
            }
        }
 
        // if all characters matched, i.e,
        // there is a substring of 'a'
        // which is same as string 'b'
        if ($j == $m)
        {
            $count++;
 
            // increment i to index m-1
            // such that minimum characters
            // are replaced in 'a'
            $i = $i + $m - 1;
 
        }
    }
 
    return $count;
}
 
// Driver Code
$str1 = "aaaaaaaa";
$str2 = "aaa";
 
echo (replace($str1, $str2));
 
// This code is contributed
// by Kirti_Mangal
?>

Javascript

<script>
// JavaScript implementation of above approach
 
// function to calculate minimum
// characters to replace
function replace(A,B)
{
 
    let n = A.length, m = B.length;
    let count = 0, i, j;
 
    for (i = 0; i < n; i++) {
        for (j = 0; j < m; j++) {
 
            // mismatch occurs
            if (A[i + j] != B[j])
                break;
        }
 
        // if all characters matched, i.e,
        // there is a substring of 'a' which
        // is same as string 'b'
        if (j == m) {
            count++;
 
             // increment i to index m-1 such that
            // minimum characters are replaced
            // in 'a'
            i += m - 1;
            
        }
    }
 
    return count;
}
 
// Driver Code
 
const str1 = "aaaaaaaa";
const str2 = "aaa";
 
document.write(replace(str1 , str2));
 
// This code is contributed by shinjanpatra.
</script>
Producción: 

2

 

Complejidad de tiempo: O(len1 * len2) , donde len1 es la longitud de la primera string y len2 es la longitud de la segunda string.
Además, este problema se puede resolver directamente usando la función incorporada de Python : string1.count(string2) 
 

Python3

// Python program to find minimum numbers
// of characters to be replaced to
// remove the given substring
str1 = "aaaaaaaa"
str2 = "aaa"
 
# inbuilt function
answer = str1.count(str2)
print(answer)
Producción: 

2

 

Publicación traducida automáticamente

Artículo escrito por aman0309 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *