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