Dada una string S y una string T , la tarea es encontrar la longitud mínima posible a la que se puede reducir la string S después de eliminar todas las apariciones posibles de la string T como una substring en la string S .
Ejemplos:
Entrada: S = “aabcbcbd”, T = “abc”
Salida: 2
Explicación:
elimina la substring {S[1], …, S[3]} y modifica la string restante a “abcbd”.
Eliminando la substring {S[0] .. S[2]}, la string resultante se modifica a «bd».
Por lo tanto, la respuesta requerida es 2.Entrada: S = “asdfbc”, T = “xyz”
Salida: 0
Explicación:
No aparece la string “xyz” como substring en S.
Enfoque: la idea es iterar sobre los caracteres de la string dada e inicializar una string auxiliar y verificar si la string recién formada está presente como una substring en la string dada. Si se determina que es cierto, simplemente elimine esa substring de la string dada.
Siga los pasos a continuación para resolver este problema:
- Primero, identifique las substrings T recorriendo la string y haciendo un seguimiento de los caracteres encontrados.
- Pero, cuando se elimina la substring, la concatenación de las partes restantes es costosa ya que cada carácter tiene que retroceder M lugares.
- Para evitar esto, mantenga una string, digamos temp , que contenga solo los caracteres iterados hasta el momento.
- Por lo tanto, si la substring requerida está presente en temp , simplemente elimine los últimos M caracteres en un tiempo computacional constante.
- Finalmente, imprima la longitud minimizada de la string después de realizar todas las operaciones.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
// Function to minimize length of
// string S after removing all
// occurrences of string T as substring
void minLength(string& S, string& T,
int N, int M)
{
string temp;
// Count of characters
// required to be removed
int subtract = 0;
// Iterate over the string
for (int i = 0; i < N; ++i) {
// Insert the current
// character to temp
temp.push_back(S[i]);
// Check if the last M
// characters forms t or not
if (temp.size() >= M) {
// Getting the last M
// characters. If they
// are equal to t then
// remove the last M
// characters from the temp string
if (temp.substr(temp.size() - M, M) == T) {
// Incrementing subtract by M
subtract += M;
// Removing last M
// characters from the
// string
int cnt = 0;
while (cnt != M) {
temp.pop_back();
++cnt;
}
}
}
}
// Print the final answer
cout << (N - subtract) << "\n";
}
// Driver Code
int main()
{
// Given string S & T
string S = "aabcbcbd", T = "abc";
// Length of string S
int N = S.size();
// Length of string T
int M = T.size();
// Prints the count of
// operations required
minLength(S, T, N, M);
}
Java
// Java program for the above approach
import java.io.*;
import java.util.*;
class GFG{
// Function to minimize length of
// string S after removing all
// occurrences of string T as substring
static void minLength(String S, String T,
int N, int M)
{
String temp = "";
// Count of characters
// required to be removed
int subtract = 0;
// Iterate over the string
for(int i = 0; i < N; ++i)
{
// Insert the current
// character to temp
temp += S.charAt(i);
// Check if the last M
// characters forms t or not
if (temp.length() >= M)
{
// Getting the last M characters.
// If they are equal to t then
// remove the last M characters
// from the temp string
if (T.equals(
temp.substring(temp.length() - M,
temp.length())))
{
// Incrementing subtract by M
subtract += M;
// Removing last M
// characters from the
// string
int cnt = 0;
while (cnt != M)
{
temp = temp.substring(
0, temp.length() - 1);
++cnt;
}
}
}
}
// Print the final answer
System.out.println((N - subtract));
}
// Driver Code
public static void main(String[] args)
{
// Given string S & T
String S = "aabcbcbd", T = "abc";
// Length of string S
int N = S.length();
// Length of string T
int M = T.length();
// Prints the count of
// operations required
minLength(S, T, N, M);
}
}
// This code is contributed by Dharanendra L V
Python3
# Python program for the above approach # Function to minimize length of # string S after removing all # occurrences of string T as substring def minLength(S, T, N, M): temp = ""; # Count of characters # required to be removed subtract = 0; # Iterate over the string for i in range(N): # Insert the current # character to temp temp += S[i]; # Check if the last M # characters forms t or not if (len(temp) >= M): # Getting the last M characters. # If they are equal to t then # remove the last M characters # from the temp string if (T ==(temp[len(temp) - M: len(temp)])): # Incrementing subtract by M subtract += M; # Removing last M # characters from the # string cnt = 0; while (cnt != M): temp = temp[0: len(temp) - 1]; cnt+= 1; # Print the final answer print((N - subtract)); # Driver Code if __name__ == '__main__': # Given string S & T S = "aabcbcbd"; T = "abc"; # Length of string S N = len(S); # Length of string T M = len(T); # Prints the count of # operations required minLength(S, T, N, M); # This code is contributed by 29AjayKumar
C#
// C# program for the above approach
using System;
class GFG{
// Function to minimize length of
// string S after removing all
// occurrences of string T as substring
static void minLength(String S, String T,
int N, int M)
{
String temp = "";
// Count of characters
// required to be removed
int subtract = 0;
// Iterate over the string
for(int i = 0; i < N; ++i)
{
// Insert the current
// character to temp
temp += S[i];
// Check if the last M
// characters forms t or not
if (temp.Length >= M)
{
// Getting the last M characters.
// If they are equal to t then
// remove the last M characters
// from the temp string
if (T.Equals(
temp.Substring(temp.Length - M, M)))
{
// Incrementing subtract by M
subtract += M;
// Removing last M
// characters from the
// string
int cnt = 0;
while (cnt != M)
{
temp = temp.Substring(
0, temp.Length - 1);
++cnt;
}
}
}
}
// Print the readonly answer
Console.WriteLine((N - subtract));
}
// Driver Code
public static void Main(String[] args)
{
// Given string S & T
String S = "aabcbcbd", T = "abc";
// Length of string S
int N = S.Length;
// Length of string T
int M = T.Length;
// Prints the count of
// operations required
minLength(S, T, N, M);
}
}
// This code is contributed by shikhasingrajput
Javascript
<script>
// Javascript program of the above approach
// Function to minimize length of
// string S after removing all
// occurrences of string T as substring
function minLength(S, T,
N, M)
{
let temp = "";
// Count of characters
// required to be removed
let subtract = 0;
// Iterate over the string
for(let i = 0; i < N; ++i)
{
// Insert the current
// character to temp
temp += S[i];
// Check if the last M
// characters forms t or not
if (temp.length >= M)
{
// Getting the last M characters.
// If they are equal to t then
// remove the last M characters
// from the temp string
if (T ==
temp.substr(temp.length - M,
temp.length))
{
// Incrementing subtract by M
subtract += M;
// Removing last M
// characters from the
// string
let cnt = 0;
while (cnt != M)
{
temp = temp.substr(
0, temp.length - 1);
++cnt;
}
}
}
}
// Print the final answer
document.write((N - subtract));
}
// Driver Code
// Given string S & T
let S = "aabcbcbd", T = "abc";
// Length of string S
let N = S.length;
// Length of string T
let M = T.length;
// Prints the count of
// operations required
minLength(S, T, N, M);
</script>
Producción:
2
Complejidad temporal: O(N)
Espacio auxiliar: O(N)
Publicación traducida automáticamente
Artículo escrito por shreyasshetty788 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA