Minimice la extracción o las inserciones necesarias para hacer que dos strings sean iguales

Dadas dos strings S y T , ambas de longitud N y S es un anagrama de la string T , la tarea es convertir la string S en T realizando las siguientes operaciones un número mínimo de veces:

• Elimina un carácter de cualquier extremo.
• Inserta un carácter en cualquier posición.

Imprime el conteo del número mínimo de operaciones requeridas.
 

Ejemplos:

Entrada: S = “qpmon”, T = “mnopq”
Salida: 3
Explicación: 
Operación 1: Retire ‘n’ del final e insértela en la penúltima posición. La string S se modifica a «qpmno». 
Operación 2: elimine la ‘q’ del principio e insértela en la última posición. La string S se modifica a «pmnoq». 
Operación 3: elimine la ‘p’ del principio e insértela en la penúltima posición. La string S se modifica a «mnopq», que es lo mismo que la string deseada T.

Entrada: S = “abab”, T = “baba”
Salida: 1

Enfoque: El problema dado se puede resolver mediante la siguiente observación: 

• Se requiere encontrar la longitud de la substring más larga de A que es una subsecuencia en B. Deje que la longitud de esa substring sea L .
• Luego, los caracteres restantes se pueden insertar sin alterar el orden existente.
• Para concluir, la respuesta óptima será igual a N – L.

 Por lo tanto, a partir de las observaciones anteriores, el número mínimo de operaciones requeridas es la diferencia entre N y la longitud de la substring más larga de la string A ,  que es una subsecuencia en la string B.

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

// C++ program for the above approach
 
#include <bits/stdc++.h>
using namespace std;
 
// Function to find the longest substring
// in string A which is a subsequence in B
int findLongestSubstring(
    int posA, int posB, string& A,
    string& B, bool canSkip, int n,
    vector<vector<vector<int> > >& dp)
{
 
    // If the indices are out of bounds
    if (posA >= n || posB >= n) {
        return 0;
    }
 
    // If an already computed subproblem occurred
    if (dp[posA][posB][canSkip] != -1) {
        return dp[posA][posB][canSkip];
    }
 
    // Required answer if the all the
    // characters of A and B are the same
    int op1 = 0;
 
    // Required answer if there is no
    // substring A which is a
    //  subsequence in B
    int op2 = 0;
 
    // Required answer if the current
    // character in B is skipped
    int op3 = 0;
 
    if (A[posA] == B[posB]) {
        op1 = 1 + findLongestSubstring(
                      posA + 1, posB + 1, A,
                      B, 0, n, dp);
    }
    if (canSkip) {
        op2 = findLongestSubstring(
            posA + 1, posB, A, B,
            canSkip, n, dp);
    }
    op3 = findLongestSubstring(
        posA, posB + 1, A, B,
        canSkip, n, dp);
 
    // The answer for the subproblem is
    // the maximum among the three
    return dp[posA][posB][canSkip]
           = max(op1, max(op2, op3));
}
 
// Function to return the minimum strings
// operations required to make two strings equal
void minOperations(string A, string B, int N)
{
    // Initialize the dp vector
    vector<vector<vector<int> > > dp(
        N, vector<vector<int> >(
               N, vector<int>(2, -1)));
 
    cout << N - findLongestSubstring(
                    0, 0, A, B, 1, N, dp);
}
 
// Driver Code
int main()
{
    string A = "abab";
    string B = "baba";
 
    int N = A.size();
 
    minOperations(A, B, N);
 
    return 0;
}

// Java program for the above approach
import java.io.*;
import java.util.*;
class GFG {
 
  // Function to find the longest substring
  // in string A which is a subsequence in B
  static int
    findLongestSubstring(int posA, int posB, String A,
                         String B, int canSkip, int n,
                         int dp[][][])
  {
 
    // If the indices are out of bounds
    if (posA >= n || posB >= n)
    {
      return 0;
    }
 
    // If an already computed subproblem occurred
    if (dp[posA][posB][canSkip] != -1)
    {
      return dp[posA][posB][canSkip];
    }
 
    // Required answer if the all the
    // characters of A and B are the same
    int op1 = 0;
 
    // Required answer if there is no
    // substring A which is a
    //  subsequence in B
    int op2 = 0;
 
    // Required answer if the current
    // character in B is skipped
    int op3 = 0;
    if (A.charAt(posA) == B.charAt(posB))
    {
      op1 = 1
        + findLongestSubstring(posA + 1, posB + 1,
                               A, B, 0, n, dp);
    }
    if (canSkip == 1) {
      op2 = findLongestSubstring(posA + 1, posB, A, B,
                                 canSkip, n, dp);
    }
    op3 = findLongestSubstring(posA, posB + 1, A, B,
                               canSkip, n, dp);
 
    // The answer for the subproblem is
    // the maximum among the three
    return dp[posA][posB][canSkip]
      = Math.max(op1, Math.max(op2, op3));
  }
 
  // Function to return the minimum strings
  // operations required to make two strings equal
  static void minOperations(String A, String B, int N)
  {
    // Initialize the dp vector
    int[][][] dp = new int[N][N][2];
 
    for(int i = 0; i < N; i++)
    {
      for(int j = 0; j < N; j++)
      {        
        for(int k = 0; k < 2; k++)
        {    
          dp[i][j][k] = -1;
        }
      }
    }
 
    System.out.println(
      N - findLongestSubstring(0, 0, A, B, 1, N, dp));
  }
 
  // Driver Code
  public static void main(String[] args)
  {
    String A = "abab";
    String B = "baba";
    int N = A.length();
    minOperations(A, B, N);
  }
}
 
// This code is contributed by Dharanendra L V

# Python3 program for the above approach
 
# Function to find the longest substring
# in A which is a subsequence in B
def findLongestSubstring(posA, posB, A, B, canSkip, n):
    global dp
    if (posA >= n or posB >= n):
        return 0
 
    # If an already computed subproblem occurred
    if (dp[posA][posB][canSkip] != -1):
        return dp[posA][posB][canSkip]
 
    # Required answer if the all the
    # characters of A and B are the same
    op1 = 0
 
    # Required answer if there is no
    # subA which is a
    # subsequence in B
    op2 = 0
 
    # Required answer if the current
    # character in B is skipped
    op3 = 0
 
    if (A[posA] == B[posB]):
        op1 = 1 + findLongestSubstring(posA + 1, posB + 1, A, B, 0, n)
    if (canSkip):
        op2 = findLongestSubstring(posA + 1, posB, A, B, canSkip, n)
 
    op3 = findLongestSubstring(posA, posB + 1, A, B, canSkip, n)
 
    # The answer for the subproblem is
    # the maximum among the three
    dp[posA][posB][canSkip] = max(op1, max(op2, op3))
    return dp[posA][posB][canSkip]
 
# Function to return the minimum strings
# operations required to make two strings equal
def minOperations(A, B, N):
    print(N - findLongestSubstring(0, 0, A, B, 1, N))
 
# Driver Code
if __name__ == '__main__':
    A = "abab"
    B = "baba"
    dp = [[[-1, -1] for i in range(len(A))] for i in range(len(A))]
    N = len(A)
    minOperations(A, B, N)
     
# This code is contributed by mohit kumar 29.

// C# program for the above approach
using System;
class GFG
{
 
      // Function to find the longest substring
    // in string A which is a subsequence in B
    static int
    findLongestSubstring(int posA, int posB, String A,
                         String B, int canSkip, int n,
                         int[, , ] dp)
    {
 
        // If the indices are out of bounds
        if (posA >= n || posB >= n) {
            return 0;
        }
 
        // If an already computed subproblem occurred
        if (dp[posA, posB, canSkip] != -1) {
            return dp[posA, posB, canSkip];
        }
 
        // Required answer if the all the
        // characters of A and B are the same
        int op1 = 0;
 
        // Required answer if there is no
        // substring A which is a
        //  subsequence in B
        int op2 = 0;
 
        // Required answer if the current
        // character in B is skipped
        int op3 = 0;
 
        if (A[posA] == B[posB]) {
            op1 = 1
                  + findLongestSubstring(posA + 1, posB + 1,
                                         A, B, 0, n, dp);
        }
        if (canSkip == 1) {
            op2 = findLongestSubstring(posA + 1, posB, A, B,
                                       canSkip, n, dp);
        }
        op3 = findLongestSubstring(posA, posB + 1, A, B,
                                   canSkip, n, dp);
 
        // The answer for the subproblem is
        // the maximum among the three
        return dp[posA, posB, canSkip]
            = Math.Max(op1, Math.Max(op2, op3));
    }
 
    // Function to return the minimum strings
    // operations required to make two strings equal
    static void minOperations(String A, String B, int N)
    {
        // Initialize the dp vector
        int[, , ] dp = new int[N, N, 2];
           
          for(int i = 0; i < N; i++)
        {      
              for(int j = 0; j < N; j++)
            {               
                  for(int k = 0; k < 2; k++)
                {    
                      dp[i, j, k] = -1;
                }
            }
        }
        Console.WriteLine(
            N - findLongestSubstring(0, 0, A, B, 1, N, dp));
    }
 
    // Driver Code
    static public void Main ()
    {
        String A = "abab";
        String B = "baba";
        int N = A.Length;
        minOperations(A, B, N);
    }
}
 
// This code is contributed by Dharanendra L V

<script>
 
// JavaScript program for the above approach
 
// Function to find the longest substring
// in string A which is a subsequence in B
function findLongestSubstring( posA, posB, A, B, canSkip, n, dp)
{
 
    // If the indices are out of bounds
    if (posA >= n || posB >= n) {
        return 0;
    }
 
    // If an already computed subproblem occurred
    if (dp[posA][posB][canSkip] != -1) {
        return dp[posA][posB][canSkip];
    }
 
    // Required answer if the all the
    // characters of A and B are the same
    var op1 = 0;
 
    // Required answer if there is no
    // substring A which is a
    //  subsequence in B
    var op2 = 0;
 
    // Required answer if the current
    // character in B is skipped
    var op3 = 0;
 
    if (A[posA] == B[posB]) {
        op1 = 1 + findLongestSubstring(
                      posA + 1, posB + 1, A,
                      B, 0, n, dp);
    }
    if (canSkip) {
        op2 = findLongestSubstring(
            posA + 1, posB, A, B,
            canSkip, n, dp);
    }
    op3 = findLongestSubstring(
        posA, posB + 1, A, B,
        canSkip, n, dp);
 
    // The answer for the subproblem is
    // the maximum among the three
    return dp[posA][posB][canSkip]
           = Math.max(op1, Math.max(op2, op3));
}
 
// Function to return the minimum strings
// operations required to make two strings equal
function minOperations(A, B, N)
{
    // Initialize the dp vector
    var dp = Array.from(Array(N), ()=> Array(N));
     
    for(var i =0; i<N; i++)
        for(var j =0; j<N; j++)
            dp[i][j] = new Array(2).fill(-1);
     
 
    document.write( N - findLongestSubstring(
                    0, 0, A, B, 1, N, dp));
}
 
// Driver Code
var A = "abab";
var B = "baba";
var N = A.length;
minOperations(A, B, N);
 
 
</script>

1

Complejidad de tiempo: O(N ² )
Complejidad de espacio: O(N ² )