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