Operaciones mínimas para transformar una string dada en otra moviendo caracteres al frente o al final

Dadas dos strings S y T de longitud N que consisten en alfabetos en minúsculas, que son permutaciones entre sí, la tarea es imprimir el número mínimo de operaciones para convertir S en T. En una operación, seleccione cualquier carácter de la string S y muévalo al principio o al final de la string S .

Ejemplos:

Entrada: S = “abcde”, T = “edacb”
Salida: 3
Explicación:
Podemos convertir S a T en 3 movimientos:
1. Mueva ‘d’ para comenzar: “dabce” 
2. Mueva ‘e’ para comenzar: “ edacb” 
3. mover ‘b’ al final: “edacb”

Entrada: S = “dcdb”, T = “ddbc”
Salida: 1
Explicación:
Mover ‘c’ al final

Enfoque ingenuo: El enfoque ingenuo consiste en probar todas las posibilidades de intercambiar un personaje. Uno puede poner algún personaje al frente, al final, o puede dejarlo en la misma posición. Las tres operaciones anteriores se pueden resolver usando recursividade imprima el número mínimo de pasos necesarios después de todos los pasos.
Complejidad de tiempo: O(3 ^N ), donde N es la longitud de la string dada.
Espacio Auxiliar: O(1)

Enfoque eficiente: para optimizar el enfoque anterior, la idea es observar que después de mover los caracteres de la string S , los caracteres sin cambios se unen para formar una substring contigua en T . Entonces, si podemos maximizar la longitud de esta subsecuencia, entonces el conteo de operaciones para convertir la string S a T es:

N: longitud de la substring contigua más larga de T que es una subsecuencia de S

Por lo tanto, para encontrar la longitud de la substring contigua más larga de T que es una subsecuencia de la string S , encuentre la subsecuencia común más larga de S y T. Deje que dp[][] almacene la longitud de la substring contigua más larga de T que es una subsecuencia de la string S , . Ahora dp[i][j] almacenará la longitud del sufijo más largo de T[0, …, j] que también es una subsecuencia de S[0, …, i] . La relación de recurrencia está dada por: 

• Si i es mayor que 0, dp[i][j] = max(dp[i-1][j], dp[i][j]).
• Si S[i] es igual a T[i] entonces, dp[i][j] = 1 + dp[i-1][j-1].

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

// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
 
int dp[1010][1010];
 
// Function that finds the minimum number
// of steps to find the minimum characters
// must be moved to convert string s to t
int solve(string s, string t)
{
 
    int n = s.size();
 
    // r = maximum value over all
    // dp[i][j] computed so far
    int r = 0;
 
    // dp[i][j] stores the longest
    // contiguous suffix of T[0..j]
    // that is subsequence of S[0..i]
    for (int i = 0; i < n; i++) {
 
        for (int j = 0; j < n; j++) {
 
            dp[i][j] = 0;
            if (i > 0) {
 
                dp[i][j] = max(dp[i - 1][j],
                               dp[i][j]);
            }
            if (s[i] == t[j]) {
 
                int ans = 1;
                if (i > 0 && j > 0) {
 
                    ans = 1 + dp[i - 1][j - 1];
                }
 
                // Update the maximum length
                dp[i][j] = max(dp[i][j], ans);
                r = max(r, dp[i][j]);
            }
        }
    }
 
    // Return the resulting length
    return (n - r);
}
 
// Driver Code
int main()
{
    // Given string s, t
    string s = "abcde";
    string t = "edacb";
 
    // Function Call
    cout << solve(s, t);
    return 0;
}

// Java program for the above approach
class GFG{
    static int[][] dp = new int[1010][1010];
 
    // Function that finds the minimum number
    // of steps to find the minimum characters
    // must be moved to convert String s to t
    static int solve(String s, String t)
    {
        int n = s.length();
 
        // r = maximum value over all
        // dp[i][j] computed so far
        int r = 0;
 
        // dp[i][j] stores the longest
        // contiguous suffix of T[0..j]
        // that is subsequence of S[0..i]
        for (int i = 0; i < n; i++)
        {
            for (int j = 0; j < n; j++)
            {
                dp[i][j] = 0;
                if (i > 0)
                {
                    dp[i][j] = Math.max(dp[i - 1][j],
                                        dp[i][j]);
                }
                if (s.charAt(i) == t.charAt(j))
                {
                    int ans = 1;
                    if (i > 0 && j > 0)
                    {
                        ans = 1 + dp[i - 1][j - 1];
                    }
 
                    // Update the maximum length
                    dp[i][j] = Math.max(dp[i][j], ans);
                    r = Math.max(r, dp[i][j]);
                }
            }
        }
 
        // Return the resulting length
        return (n - r);
    }
 
    // Driver Code
    public static void main(String[] args)
    {
        // Given String s, t
        String s = "abcde";
        String t = "edacb";
 
        // Function Call
        System.out.print(solve(s, t));
    }
}
 
// This code is contributed by shikhasingrajput

# Python3 program for the above approach
dp = [[0] * 1010] * 1010
 
# Function that finds the minimum number
# of steps to find the minimum characters
# must be moved to convert string s to t
def solve(s, t):
 
    n = len(s)
 
    # r = maximum value over all
    # dp[i][j] computed so far
    r = 0
 
    # dp[i][j] stores the longest
    # contiguous suffix of T[0..j]
    # that is subsequence of S[0..i]
    for j in range(0, n):
        for i in range(0, n):
            dp[i][j] = 0
             
            if (i > 0):
                dp[i][j] = max(dp[i - 1][j],
                               dp[i][j])
             
            if (s[i] == t[j]):
                ans = 1
                if (i > 0 and j > 0):
                    ans = 1 + dp[i - 1][j - 1]
                 
                # Update the maximum length
                dp[i][j] = max(dp[i][j], ans)
                r = max(r, dp[i][j])
                 
    # Return the resulting length
    return (n - r)
 
# Driver Code
 
# Given string s, t
s = "abcde"
t = "edacb"
 
# Function call
print(solve(s, t))
 
# This code is contributed by code_hunt

// C# program for the above approach
using System;
class GFG{
static int[, ] dp = new int[1010, 1010];
 
// Function that finds the minimum number
// of steps to find the minimum characters
// must be moved to convert String s to t
static int solve(String s, String t)
{
    int n = s.Length;
 
    // r = maximum value over all
    // dp[i, j] computed so far
    int r = 0;
 
    // dp[i, j] stores the longest
    // contiguous suffix of T[0..j]
    // that is subsequence of S[0..i]
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < n; j++)
        {
            dp[i, j] = 0;
            if (i > 0)
            {
                dp[i, j] = Math.Max(dp[i - 1, j],
                                    dp[i, j]);
            }
            if (s[i] == t[j])
            {
                int ans = 1;
                if (i > 0 && j > 0)
                {
                    ans = 1 + dp[i - 1, j - 1];
                }
 
                // Update the maximum length
                dp[i, j] = Math.Max(dp[i, j], ans);
                r = Math.Max(r, dp[i, j]);
            }
        }
    }
 
    // Return the resulting length
    return (n - r);
}
 
// Driver Code
public static void Main(String[] args)
{
        
    // Given String s, t
    String s = "abcde";
    String t = "edacb";
 
    // Function Call
    Console.Write(solve(s, t));
}
}
 
// This code is contributed by shikhasingrajput

<script>
 
// Javascript program for the above approach
 
var dp = Array.from(Array(1010), ()=> Array(1010));
 
// Function that finds the minimum number
// of steps to find the minimum characters
// must be moved to convert string s to t
function solve(s, t)
{
 
    var n = s.length;
 
    // r = maximum value over all
    // dp[i][j] computed so far
    var r = 0;
 
    // dp[i][j] stores the longest
    // contiguous suffix of T[0..j]
    // that is subsequence of S[0..i]
    for (var i = 0; i < n; i++) {
 
        for (var j = 0; j < n; j++) {
 
            dp[i][j] = 0;
            if (i > 0) {
 
                dp[i][j] = Math.max(dp[i - 1][j],
                               dp[i][j]);
            }
            if (s[i] == t[j]) {
 
                var ans = 1;
                if (i > 0 && j > 0) {
 
                    ans = 1 + dp[i - 1][j - 1];
                }
 
                // Update the maximum length
                dp[i][j] = Math.max(dp[i][j], ans);
                r = Math.max(r, dp[i][j]);
            }
        }
    }
 
    // Return the resulting length
    return (n - r);
}
 
// Driver Code
// Given string s, t
var s = "abcde";
var t = "edacb";
// Function Call
document.write( solve(s, t));
 
</script>

3

Complejidad de tiempo: O(N ² ), donde N es la longitud de la string dada
Espacio auxiliar: O(N ² )

Nota: El enfoque ingenuo anterior es eficiente para strings más pequeñas, mientras que el enfoque eficiente anterior es eficiente para strings más grandes.