Dadas dos strings S1 y S2 de longitud N y M respectivamente , que consisten en letras minúsculas, la tarea es encontrar la longitud mínima a la que se puede reducir S1 eliminando todas las ocurrencias de la string S2 de la string S1 .
Ejemplos:
Entrada: S1 =”fffoxoxoxfxo”, S2 = “zorro”;
Salida: 3
Explicación:
Al eliminar «zorro» a partir del índice 2, la string se modifica a «ffoxoxfxo».
Al eliminar «fox» a partir del índice 1, la string se modifica a «foxfxo».
Al eliminar «zorro» a partir del índice 0, la string se modifica a «fxo».
Por lo tanto, la longitud mínima de la string S1 después de eliminar todas las ocurrencias de S2 es 3.Entrada: S1 =”abcd”, S2 = “pqr”
Salida: 4
Enfoque: La idea para resolver este problema es utilizar Stack Data Structure . Siga los pasos a continuación para resolver el problema dado:
- Inicialice una pila para almacenar los caracteres de la string S1 en ella.
- Atraviese la string S1 dada y realice las siguientes operaciones:
- Empuje el carácter actual en la pila.
- Si el tamaño de la pila es al menos M , compruebe si los M caracteres superiores de la pila forman la string S2 o no. Si se determina que es cierto, elimine esos caracteres.
- Después de completar los pasos anteriores, el tamaño restante de la pila es la longitud mínima requerida.
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 find the minimum length
// to which string str can be reduced to
// by removing all occurrences of string K
int minLength(string str, int N,
string K, int M)
{
// Initialize stack of characters
stack<char> stackOfChar;
for (int i = 0; i < N; i++) {
// Push character into the stack
stackOfChar.push(str[i]);
// If stack size >= K.size()
if (stackOfChar.size() >= M) {
// Create empty string to
// store characters of stack
string l = "";
// Traverse the string K in reverse
for (int j = M - 1; j >= 0; j--) {
// If any of the characters
// differ, it means that K
// is not present in the stack
if (K[j] != stackOfChar.top()) {
// Push the elements
// back into the stack
int f = 0;
while (f != l.size()) {
stackOfChar.push(l[f]);
f++;
}
break;
}
// Store the string
else {
l = stackOfChar.top()
+ l;
// Remove top element
stackOfChar.pop();
}
}
}
}
// Size of stack gives the
// minimized length of str
return stackOfChar.size();
}
// Driver Code
int main()
{
string S1 = "fffoxoxoxfxo";
string S2 = "fox";
int N = S1.length();
int M = S2.length();
// Function Call
cout << minLength(S1, N, S2, M);
return 0;
}
Java
// Java program for the above approach
import java.util.*;
class GFG
{
// Function to find the minimum length
// to which String str can be reduced to
// by removing all occurrences of String K
static int minLength(String str, int N,
String K, int M)
{
// Initialize stack of characters
Stack<Character> stackOfChar = new Stack<Character>();
for (int i = 0; i < N; i++)
{
// Push character into the stack
stackOfChar.add(str.charAt(i));
// If stack size >= K.size()
if (stackOfChar.size() >= M)
{
// Create empty String to
// store characters of stack
String l = "";
// Traverse the String K in reverse
for (int j = M - 1; j >= 0; j--)
{
// If any of the characters
// differ, it means that K
// is not present in the stack
if (K.charAt(j) != stackOfChar.peek())
{
// Push the elements
// back into the stack
int f = 0;
while (f != l.length())
{
stackOfChar.add(l.charAt(f));
f++;
}
break;
}
// Store the String
else
{
l = stackOfChar.peek()
+ l;
// Remove top element
stackOfChar.pop();
}
}
}
}
// Size of stack gives the
// minimized length of str
return stackOfChar.size();
}
// Driver Code
public static void main(String[] args)
{
String S1 = "fffoxoxoxfxo";
String S2 = "fox";
int N = S1.length();
int M = S2.length();
// Function Call
System.out.print(minLength(S1, N, S2, M));
}
}
// This code is contributed by 29AjayKumar
Python3
# Python3 program for the above approach # Function to find the minimum length # to which string str can be reduced to # by removing all occurrences of string K def minLength(Str, N, K, M) : # Initialize stack of characters stackOfChar = [] for i in range(N) : # Push character into the stack stackOfChar.append(Str[i]) # If stack size >= K.size() if (len(stackOfChar) >= M) : # Create empty string to # store characters of stack l = "" # Traverse the string K in reverse for j in range(M - 1, -1, -1) : # If any of the characters # differ, it means that K # is not present in the stack if (K[j] != stackOfChar[-1]) : # Push the elements # back into the stack f = 0 while (f != len(l)) : stackOfChar.append(l[f]) f += 1 break # Store the string else : l = stackOfChar[-1] + l # Remove top element stackOfChar.pop() # Size of stack gives the # minimized length of str return len(stackOfChar) # Driver code S1 = "fffoxoxoxfxo" S2 = "fox" N = len(S1) M = len(S2) # Function Call print(minLength(S1, N, S2, M)) # This code is contributed by divyeshrabadiya07
C#
// C# program for the above approach
using System;
using System.Collections.Generic;
class GFG
{
// Function to find the minimum length
// to which String str can be reduced to
// by removing all occurrences of String K
static int minLength(String str, int N,
String K, int M)
{
// Initialize stack of characters
Stack<char> stackOfChar = new Stack<char>();
for (int i = 0; i < N; i++)
{
// Push character into the stack
stackOfChar.Push(str[i]);
// If stack size >= K.Count
if (stackOfChar.Count >= M)
{
// Create empty String to
// store characters of stack
String l = "";
// Traverse the String K in reverse
for (int j = M - 1; j >= 0; j--)
{
// If any of the characters
// differ, it means that K
// is not present in the stack
if (K[j] != stackOfChar.Peek())
{
// Push the elements
// back into the stack
int f = 0;
while (f != l.Length)
{
stackOfChar.Push(l[f]);
f++;
}
break;
}
// Store the String
else
{
l = stackOfChar.Peek()
+ l;
// Remove top element
stackOfChar.Pop();
}
}
}
}
// Size of stack gives the
// minimized length of str
return stackOfChar.Count;
}
// Driver Code
public static void Main(String[] args)
{
String S1 = "fffoxoxoxfxo";
String S2 = "fox";
int N = S1.Length;
int M = S2.Length;
// Function Call
Console.Write(minLength(S1, N, S2, M));
}
}
// This code is contributed by 29AjayKumar
Javascript
<script>
// JavaScript program for the above approach
// Function to find the minimum length
// to which string str can be reduced to
// by removing all occurrences of string K
function minLength(str, N, K, M)
{
// Initialize stack of characters
var stackOfChar = [];
for (var i = 0; i < N; i++) {
// Push character into the stack
stackOfChar.push(str[i]);
// If stack size >= K.size()
if (stackOfChar.length >= M) {
// Create empty string to
// store characters of stack
var l = "";
// Traverse the string K in reverse
for (var j = M - 1; j >= 0; j--) {
// If any of the characters
// differ, it means that K
// is not present in the stack
if (K[j] != stackOfChar[stackOfChar.length-1]) {
// Push the elements
// back into the stack
var f = 0;
while (f != l.length) {
stackOfChar.push(l[f]);
f++;
}
break;
}
// Store the string
else {
l = stackOfChar[stackOfChar.length-1]
+ l;
// Remove top element
stackOfChar.pop();
}
}
}
}
// Size of stack gives the
// minimized length of str
return stackOfChar.length;
}
// Driver Code
var S1 = "fffoxoxoxfxo";
var S2 = "fox";
var N = S1.length;
var M = S2.length;
// Function Call
document.write( minLength(S1, N, S2, M));
</script>
Producción:
3
Complejidad de tiempo: O(N*M), ya que estamos usando bucles anidados para atravesar N*M veces.
Espacio auxiliar: O(N), ya que estamos usando espacio adicional para la pila.