Dadas dos strings A y B , imprima el número mínimo de rebanadas requeridas en A para obtener otra string B. En caso de que no sea posible obtener B de A , imprima «-1».
Ejemplos:
Entrada: A = “geeksforgeeks”, B = “ksgek”
Salida: 5
Explicación: g | ee | k | fragua | ek | s : se requieren un mínimo de 5 cortes para crear BEntrada: A = “topgames”, B = “mepo”
Salida: 5
Explicación: t | o | pag | ga | yo | s: se requieren un mínimo de 5 cortes para crear BEntrada: A = “memk”, B = “memo”
Salida: -1
Explicación: No es posible crear B con la ayuda de A
Enfoque: este problema es una variación del problema de la substring común más larga . La idea principal para resolver este problema es obtener la substring común más larga entre A y B y luego decidir sobre la base del índice de inicio de la substring común en A , el número de cortes necesarios para cortar esa porción de A . Luego saque esa porción de A con 1 o 2 rebanadas. Además, elimine esa substring de B y reemplácela con «0» o cualquier otra cosa que no sean alfabetos en el caso de A . Ahora, siga los pasos a continuación para resolver este problema:
- Primero, haga una verificación simple con longitudes de A y B. Si B es más largo, devuelve -1.
- Ahora el primer paso es encontrar la substring común más larga en ambas strings.
- Ahora, si el índice inicial o el índice final de esa substring común en la String A es 0 o N (A.length()-1) respectivamente, entonces en ese solo se necesita 1 segmento para cortar esa porción.
Por ejemplo: A = “juego” y B = “ga” luego ga | yo. Solo se requiere una rebanada
- Si la substring está entre el primer y el último carácter de la string A , en ese caso, se requieren 2 segmentos para cortar esa parte.
Por ejemplo: A = “jugador” y B = “yo” -> ga | yo | r Se requieren dos rebanadas
- Ahora, reduzca el tamaño de B eliminando la substring actual más larga. Es necesario hacer esto porque se elige una substring diferente como la substring común más larga en la próxima llamada de la substring más larga() .
- Después de eso, reemplace esa substring común presente en A con el carácter «0». La substring no se puede eliminar directamente de A porque el orden es importante ya que estamos usando el índice de la substring común presente en A para decidir el número de segmentos.
- Repita el mismo proceso hasta que la string B quede vacía.
A continuación se muestra la implementación del enfoque anterior:
Java
// Java program for the above approach
import java.io.*;
class GFG {
// Function returning the ending points
// of LCS and the length of LCS
public static int[] longestSubString(
String X, String Y)
{
// Find length of both the Strings.
int m = X.length();
int n = Y.length();
// Variable to store length of
// longest common subString.
int result = 0;
// Variable to store ending point of
// longest common subString in X.
int endIndexX = 0;
int endIndexY = 0;
// Matrix to store result of two
// consecutive rows at a time.
int cache[][] = new int[2][m + 1];
// Variable to represent which row of
// matrix is current row.
int currentRow = 0;
// For a particular value of i and j,
// len[currRow][j] stores length of
// longest common subString in
// String X[0..i] and Y[0..j].
for (int i = 0; i <= m; i++) {
for (int j = 0; j <= n; j++) {
if (i == 0 || j == 0) {
cache[currentRow][j] = 0;
}
else if (X.charAt(i - 1)
== Y.charAt(j - 1)) {
cache[currentRow][j]
= cache[1 -
currentRow][j
- 1]
+ 1;
if (cache[currentRow][j]
> result) {
result
= cache[currentRow][j];
endIndexX = i - 1;
endIndexY = j - 1;
}
}
else {
cache[currentRow][j] = 0;
}
}
// Make current row as previous row and
// previous row as new current row.
currentRow = 1 - currentRow;
}
// Longest common subString is from index
// (endIndexX - result + 1) in X and
// (endIndexY - result + 1) in Y.
int[] array = new int[] { (endIndexX
- result
+ 1),
(endIndexY
- result
+ 1),
result };
return array;
}
// Function to replace used substring in A with 0's
public static String processString(String A,
int index,
int length)
{
String X = A.substring(0, index);
String Y = "";
// Inserting "0" in place
// of that substring.
for (int i = 0; i < length; i++) {
Y += "0";
}
String Z = A.substring(index
+ length);
return (X + Y + Z);
}
// Function to return the minimum
// number of slices required.
public static int minimumSlice(String A,
String B)
{
// Checking the length of A and B.
if (A.length() < B.length())
return -1;
// If both are equal no slice required.
if (A.equals(B))
return 0;
int result = 0, n = (A.length() - 1);
// Loop continues until B is empty.
while (!B.isEmpty()) {
int[] processed
= longestSubString(A, B);
if (processed[2] == 0)
return -1;
// Incrementing result by 1 if
// longest substring start at index 0
// or the end point is equal to n
if ((processed[0]
+ processed[2] - 1 == n)
|| processed[0] == 0) {
// Result should only
// be incremented if
// character just before
// and after the
// substring is not "0";
// if "0" is there,
// then the slice
// has already been counted
if (processed[0] == 0) {
if (A.charAt(processed[0]
+ processed[2])
!= '0')
result++;
}
else {
if (A.charAt(processed[0] - 1)
!= '0')
result++;
}
}
// In any other case increment it by 2
else {
// Result should only
// be incremented if
// character just before
// and after the substring
// is not "0";
// if "0" is there,
// then the slice has
// already been counted.
if (A.charAt(processed[0]
+ processed[2])
!= '0') {
result++;
}
if (A.charAt(processed[0] - 1)
!= '0') {
result++;
}
}
// Reducing the size of B by
// removing current longest
// substring from it.
B = B.substring(0, processed[1])
+ B.substring(processed[1]
+ processed[2]);
// Clearing the used substring from A.
A = processString(A, processed[0],
processed[2]);
}
return result;
}
// Driver Code
public static void main(String[] args)
{
System.out.println(minimumSlice("topgames", "mepo"));
}
}
Python3
# Python 3 program for the above approach
# Function returning the ending points
# of LCS and the length of LCS
def longestSubString(
X, Y):
# Find length of both the Strings.
m = len(X)
n = len(Y)
# Variable to store length of
# longest common subString.
result = 0
# Variable to store ending point of
# longest common subString in X.
endIndexX = 0
endIndexY = 0
# Matrix to store result of two
# consecutive rows at a time.
cache = [[0 for x in range(m+1)] for y in range(2)]
# Variable to represent which row of
# matrix is current row.
currentRow = 0
# For a particular value of i and j,
# len[currRow][j] stores length of
# longest common subString in
# String X[0..i] and Y[0..j].
for i in range(m + 1):
for j in range(n + 1):
if (i == 0 or j == 0):
cache[currentRow][j] = 0
elif (X[i - 1] == Y[j - 1]):
cache[currentRow][j] = cache[1 - currentRow][j - 1] + 1
if (cache[currentRow][j]
> result):
result = cache[currentRow][j]
endIndexX = i - 1
endIndexY = j - 1
else:
cache[currentRow][j] = 0
# Make current row as previous row and
# previous row as new current row.
currentRow = 1 - currentRow
# Longest common subString is from index
# (endIndexX - result + 1) in X and
# (endIndexY - result + 1) in Y.
array = [(endIndexX
- result
+ 1),
(endIndexY
- result
+ 1),
result]
return array
# Function to replace used substring in A with 0's
def processString(A, index, length):
X = A[0: index]
Y = ""
# Inserting "0" in place
# of that substring.
for i in range(length):
Y += "0"
Z = A[index + length:]
return (X + Y + Z)
# Function to return the minimum
# number of slices required.
def minimumSlice(A,
B):
# Checking the length of A and B.
if (len(A) < len(B)):
return -1
# If both are equal no slice required.
if (A == B):
return 0
result = 0
n = (len(A) - 1)
# Loop continues until B is empty.
while (len(B) != 0):
processed = longestSubString(A, B)
if (processed[2] == 0):
return -1
# Incrementing result by 1 if
# longest substring start at index 0
# or the end point is equal to n
if ((processed[0]
+ processed[2] - 1 == n)
or processed[0] == 0):
# Result should only
# be incremented if
# character just before
# and after the
# substring is not "0"
# if "0" is there,
# then the slice
# has already been counted
if (processed[0] == 0):
if (A[processed[0] + processed[2]] != '0'):
result += 1
else:
if (A[processed[0] - 1] != '0'):
result += 1
# In any other case increment it by 2
else:
# Result should only
# be incremented if
# character just before
# and after the substring
# is not "0"
# if "0" is there,
# then the slice has
# already been counted.
if (A[processed[0]
+ processed[2]]
!= '0'):
result += 1
if (A[processed[0] - 1] != '0'):
result += 1
# Reducing the size of B by
# removing current longest
# substring from it.
B = B[0:processed[1]] + B[processed[1] + processed[2]:]
# Clearing the used substring from A.
A = processString(A, processed[0],
processed[2])
return result
# Driver Code
if __name__ == "__main__":
print(minimumSlice("topgames", "mepo"))
# This code is contributed by ukasp.
C#
// C# program for the above approach
using System;
class GFG
{
// Function returning the ending points
// of LCS and the length of LCS
public static int[] longestSubstring(string X, string Y)
{
// Find length of both the strings.
int m = X.Length;
int n = Y.Length;
// Variable to store length of
// longest common substring.
int result = 0;
// Variable to store ending point of
// longest common substring in X.
int endIndexX = 0;
int endIndexY = 0;
// Matrix to store result of two
// consecutive rows at a time.
int[,] cache = new int[2, m + 1];
// Variable to represent which row of
// matrix is current row.
int currentRow = 0;
// For a particular value of i and j,
// len[currRow][j] stores length of
// longest common substring in
// string X[0..i] and Y[0..j].
for (int i = 0; i <= m; i++)
{
for (int j = 0; j <= n; j++)
{
if (i == 0 || j == 0)
{
cache[currentRow, j] = 0;
}
else if (X[i - 1] == Y[j - 1])
{
cache[currentRow, j]
= cache[1 - currentRow, j - 1]
+ 1;
if (cache[currentRow, j]
> result)
{
result
= cache[currentRow, j];
endIndexX = i - 1;
endIndexY = j - 1;
}
}
else
{
cache[currentRow, j] = 0;
}
}
// Make current row as previous row and
// previous row as new current row.
currentRow = 1 - currentRow;
}
// Longest common substring is from index
// (endIndexX - result + 1) in X and
// (endIndexY - result + 1) in Y.
int[] array = new int[] { (endIndexX
- result
+ 1),
(endIndexY
- result
+ 1),
result };
return array;
}
// Function to replace used substring in A with 0's
public static string processstring(string A,
int index,
int length)
{
string X = A.Substring(0, index);
string Y = "";
// Inserting "0" in place
// of that substring.
for (int i = 0; i < length; i++)
{
Y += "0";
}
string Z = A.Substring(index
+ length);
return (X + Y + Z);
}
// Function to return the minimum
// number of slices required.
public static int minimumSlice(string A,
string B)
{
// Checking the length of A and B.
if (A.Length < B.Length)
return -1;
// If both are equal no slice required.
if (A.Equals(B))
return 0;
int result = 0, n = (A.Length - 1);
// Loop continues until B is empty.
while (B.Length != 0)
{
int[] processed
= longestSubstring(A, B);
if (processed[2] == 0)
return -1;
// Incrementing result by 1 if
// longest substring start at index 0
// or the end point is equal to n
if ((processed[0]
+ processed[2] - 1 == n)
|| processed[0] == 0)
{
// Result should only
// be incremented if
// character just before
// and after the
// substring is not "0";
// if "0" is there,
// then the slice
// has already been counted
if (processed[0] == 0)
{
if (A[processed[0] + processed[2]]
!= '0')
result++;
}
else
{
if (A[processed[0] - 1]
!= '0')
result++;
}
}
// In any other case increment it by 2
else
{
// Result should only
// be incremented if
// character just before
// and after the substring
// is not "0";
// if "0" is there,
// then the slice has
// already been counted.
if (A[processed[0] + processed[2]]
!= '0')
{
result++;
}
if (A[processed[0] - 1]
!= '0')
{
result++;
}
}
// Reducing the size of B by
// removing current longest
// substring from it.
B = B.Substring(0, processed[1])
+ B.Substring(processed[1]
+ processed[2]);
// Clearing the used substring from A.
A = processstring(A, processed[0],
processed[2]);
}
return result;
}
// Driver Code
public static void Main()
{
Console.Write(minimumSlice("topgames", "mepo"));
}
}
// This code is contributed by gfgking.
Producción
5
Complejidad temporal: O(N*(M 2 )) donde N es la longitud de la string A y M es la longitud de la string B
Espacio auxiliar: O(M)