Longitud de la substring más larga que se eliminará para hacer que una string sea igual a otra string

Dadas dos strings str1 y str2 , donde str2 es una subsecuencia de str1 , la tarea es encontrar la longitud de la substring más larga de str1 que, cuando se elimina, hace que las strings str2 y str1 sean iguales.

Ejemplos:

Entrada: str1 = “programmingbloods”, str2 = “ibloods”
Salida: 8
Explicación:
Las substrings que se eliminarán de str1 son [“programa”, “ng”]. Por lo tanto, la longitud de la substring eliminada más larga es 8.

Entrada: str1=“GeeksforGeeks”, str2=“tenedores”
Salida: 5

Enfoque ingenuo: el enfoque más simple es generar todas las substrings posibles de str1 y, para cada substring, eliminarla de str1 y verificar si la string resultante se vuelve igual a str2 o no. Imprime la longitud de tales substrings más largas.

Complejidad temporal: O(2 ^N )
Espacio auxiliar: O(N)

Enfoque eficiente: para optimizar el enfoque anterior, la idea es encontrar la ocurrencia de str2 en str1 . Recorra ambas strings de izquierda a derecha y verifique si ambos caracteres son iguales o no. Si es cierto, proceda a la derecha en ambas strings. De lo contrario, proceda a la derecha solo en str2 . De manera similar, para encontrar la última aparición de str2 en str1 , recorra ambas strings de derecha a izquierda y proceda de manera similar. Siga los pasos a continuación para resolver el problema:

1. Inicializar
2. Cree una array, pos[] para almacenar la posición de la primera aparición de str2 en str1.
3. Recorra ambas strings de izquierda a derecha y almacene la posición de la primera aparición de str2 eliminando algunos caracteres de str1.
4. Inicialice una variable, lastPos = length(str1)-1 para almacenar la posición del carácter actual en la última aparición de str2 eliminando algunos caracteres de str1 .
5. Atraviese ambas strings de derecha a izquierda y verifique si ambos caracteres coinciden, luego busque la posición del carácter actual de str2 en pos[]; de lo contrario, continúe.
6. Si res > ( lastPos – pos[i-1]-1), actualice res = lastPos – pos[i-1]-1.
7. Finalmente, devuelva el res .

A continuación se muestra la implementación del enfoque anterior:

// C++ Program to implement
// the above approach
 
#include <bits/stdc++.h>
using namespace std;
 
// Function to print the length
// of longest substring to be deleted
int longDelSub(string str1, string str2)
{
    // Stores the length of string
    int N = str1.size();
    int M = str2.size();
 
    // Store the position of
    // previous matched
    // character of str1
    int prev_pos = 0;
 
    // Store the position of first
    // occurrence of str2 in str1
    int pos[M];
 
    // Find the position of the
    // first occurrence of str2
    for (int i = 0; i < M; i++) {
 
        // Store the index of str1
        int index = prev_pos;
 
        // If both characters not matched
        while (index < N
               && str1[index] != str2[i]) {
            index++;
        }
 
        pos[i] = index;
        prev_pos = index + 1;
    }
 
    // Store the length of the
    // longest deleted substring
    int res = N - prev_pos;
 
    prev_pos = N - 1;
 
    // Store the position of last
    // occurrence of str2 in str1
    for (int i = M - 1; i >= 0; i--) {
        int index = prev_pos;
 
        // If both characters not matched
        while (index >= 0
               && str1[index] != str2[i]) {
            index--;
        }
 
        // Update res
        if (i != 0) {
            res = max(
                res,
                index - pos[i - 1] - 1);
        }
 
        prev_pos = index - 1;
    }
 
    // Update res.
    res = max(res, prev_pos + 1);
 
    return res;
}
 
// Driver Code
int main()
{
    // Given string
    string str1 = "GeeksforGeeks";
    string str2 = "forks";
 
    // Function Call
    cout << longDelSub(str1, str2);
    return 0;
}

// Java program to implement
// the above approach
import java.io.*;
 
class GFG{
 
// Function to print the length
// of longest substring to be deleted
static int longDelSub(String str1, String str2)
{
     
    // Stores the length of string
    int N = str1.length();
    int M = str2.length();
 
    // Store the position of
    // previous matched
    // character of str1
    int prev_pos = 0;
 
    // Store the position of first
    // occurrence of str2 in str1
    int pos[] = new int[M];
 
    // Find the position of the
    // first occurrence of str2
    for(int i = 0; i < M; i++)
    {
         
        // Store the index of str1
        int index = prev_pos;
 
        // If both characters not matched
        while (index < N &&
               str1.charAt(index) !=
               str2.charAt(i))
        {
            index++;
        }
 
        pos[i] = index;
        prev_pos = index + 1;
    }
 
    // Store the length of the
    // longest deleted substring
    int res = N - prev_pos;
 
    prev_pos = N - 1;
 
    // Store the position of last
    // occurrence of str2 in str1
    for(int i = M - 1; i >= 0; i--)
    {
        int index = prev_pos;
 
        // If both characters not matched
        while (index >= 0 &&
               str1.charAt(index) !=
               str2.charAt(i))
        {
            index--;
        }
 
        // Update res
        if (i != 0)
        {
            res = Math.max(res,
                           index -
                           pos[i - 1] - 1);
        }
        prev_pos = index - 1;
    }
 
    // Update res.
    res = Math.max(res, prev_pos + 1);
 
    return res;
}
 
// Driver Code
public static void main (String[] args)
{
     
    // Given string
    String str1 = "GeeksforGeeks";
    String str2 = "forks";
 
    // Function call
    System.out.print(longDelSub(str1, str2));
}
}
 
// This code is contributed by code_hunt

# Python3 program to implement
# the above approach
 
# Function to print the length
# of longest substring to be deleted
def longDelSub(str1, str2):
     
    # Stores the length of string
    N = len(str1)
    M = len(str2)
 
    # Store the position of
    # previous matched
    # character of str1
    prev_pos = 0
 
    # Store the position of first
    # occurrence of str2 in str1
    pos = [0] * M
 
    # Find the position of the
    # first occurrence of str2
    for i in range(M):
 
        # Store the index of str1
        index = prev_pos
 
        # If both characters not matched
        while (index < N and
          str1[index] != str2[i]):
            index += 1
         
        pos[i] = index
        prev_pos = index + 1
     
    # Store the length of the
    # longest deleted substring
    res = N - prev_pos
 
    prev_pos = N - 1
 
    # Store the position of last
    # occurrence of str2 in str1
    for i in range(M - 1, -1, -1):
        index = prev_pos
 
        # If both characters not matched
        while (index >= 0 and
          str1[index] != str2[i]):
            index -= 1
         
        # Update res
        if (i != 0) :
            res = max(res,
                      index -
                      pos[i - 1] - 1)
         
        prev_pos = index - 1
     
    # Update res.
    res = max(res, prev_pos + 1)
 
    return res
 
# Driver Code
 
# Given string
str1 = "GeeksforGeeks"
str2 = "forks"
 
# Function call
print(longDelSub(str1, str2))
 
# This code is contributed by code_hunt

// C# program to implement
// the above approach
using System;
 
class GFG{
     
// Function to print the length
// of longest substring to be deleted
static int longDelSub(string str1,
                      string str2)
{
     
    // Stores the length of string
    int N = str1.Length;
    int M = str2.Length;
 
    // Store the position of
    // previous matched
    // character of str1
    int prev_pos = 0;
 
    // Store the position of first
    // occurrence of str2 in str1
    int[] pos = new int[M];
 
    // Find the position of the
    // first occurrence of str2
    for(int i = 0; i < M; i++)
    {
 
        // Store the index of str1
        int index = prev_pos;
 
        // If both characters not matched
        while (index < N &&
          str1[index] != str2[i])
        {
            index++;
        }
 
        pos[i] = index;
        prev_pos = index + 1;
    }
 
    // Store the length of the
    // longest deleted substring
    int res = N - prev_pos;
 
    prev_pos = N - 1;
 
    // Store the position of last
    // occurrence of str2 in str1
    for(int i = M - 1; i >= 0; i--)
    {
        int index = prev_pos;
 
        // If both characters not matched
        while (index >= 0 &&
          str1[index] != str2[i])
        {
            index--;
        }
 
        // Update res
        if (i != 0)
        {
            res = Math.Max(res,
                           index -
                           pos[i - 1] - 1);
        }
        prev_pos = index - 1;
    }
 
    // Update res.
    res = Math.Max(res, prev_pos + 1);
 
    return res;
}
 
// Driver code
public static void Main()
{
     
    // Given string
    string str1 = "GeeksforGeeks";
    string str2 = "forks";
 
    // Function call
    Console.Write(longDelSub(str1, str2));
}
}
 
// This code is contributed by code_hunt

<script>
 
// JavaScript Program to implement
// the above approach
 
 
// Function to print the length
// of longest substring to be deleted
function longDelSub( str1, str2)
{
 
    // Stores the length of string
    var N = str1.length;
    var M = str2.length;
 
    // Store the position of
    // previous matched
    // character of str1
    var prev_pos = 0;
 
    // Store the position of first
    // occurrence of str2 in str1
    var pos = new Array(M);
 
    // Find the position of the
    // first occurrence of str2
    for (let i = 0; i < M; i++) {
 
        // Store the index of str1
        var index = prev_pos;
 
        // If both characters not matched
        while (index < N
            && str1[index] != str2[i]) {
            index++;
        }
 
        pos[i] = index;
        prev_pos = index + 1;
    }
 
    // Store the length of the
    // longest deleted substring
    var res = N - prev_pos;
 
    prev_pos = N - 1;
 
    // Store the position of last
    // occurrence of str2 in str1
    for (let i = M - 1; i >= 0; i--) {
        var index = prev_pos;
 
        // If both characters not matched
        while (index >= 0
            && str1[index] != str2[i]) {
            index--;
        }
 
        // Update res
        if (i != 0) {
            res = Math.max(
                res,
                index - pos[i - 1] - 1);
        }
 
        prev_pos = index - 1;
    }
 
    // Update res.
    res = Math.max(res, prev_pos + 1);
 
    return res;
}
 
// Driver Code
 
    // Given string
    var str1 = "GeeksforGeeks";
    var str2 = "forks";
 
    // Function Call
    console.log(longDelSub(str1, str2));
     
// This code is contributed by ukasp.
 
</script>

5

Complejidad temporal: O(N + M)
Espacio auxiliar: O(M)