Dadas dos strings A y B donde la string A es un anagrama de la string B. En una operación, elimine el primer o el último carácter de la string A e insértelo en cualquier posición en A . La tarea es encontrar el número mínimo de tales operaciones requeridas para convertir la string A en la string B.
Ejemplos:
Entrada: A = «edacb», B = «abcde»
Salida : 3
Explicación:
Realice las operaciones dadas de la siguiente manera:
Paso 1: Tome el último carácter ‘b’ e insértelo entre ‘a’ y ‘c’ («edacb» se convierte en » edabc” )
Paso 2: Tome el primer carácter ‘e’ insértelo al último («edabc» se convierte en «dabce») Paso
3: Tome el primer carácter ‘d’ e insértelo entre ‘c’ y ‘e’ («dabce» se convierte en «abcde» ” )
Por lo tanto, la cuenta de las operaciones es 3.Entrada: A = «abcd», B = «abdc»
Salida: 1
Explicación:
Realice las operaciones dadas de la siguiente manera:
Paso 1: Tome el último carácter ‘d’ e insértelo entre ‘b’ y ‘c’ («abcd» se convierte en » abdc” )
Por lo tanto, la cuenta de las operaciones es 1.
Enfoque: la idea es encontrar la substring más larga de la string A, que también es una subsecuencia de la string B , y restar este valor de la longitud dada de la string para obtener el recuento mínimo de operaciones requeridas.
A continuación se muestra la implementación del enfoque anterior:
C++14
// C++14 program for the above approach
#include <bits/stdc++.h>
using namespace std;
// Function to find the minimum cost
// to convert string A to string B
int minCost(string A, string B)
{
// Length of string
int n = A.size();
int i = 0;
// Initialize maxlen as 0
int maxlen = 0;
// Traverse the string A
while (i < n)
{
// Stores the length of
// substrings of string A
int length = 0;
// Traversing string B for
// each character of A
for(int j = 0; j < n; ++j)
{
// Shift i pointer towards
// right and increment length,
// if A[i] equals B[j]
if (A[i] == B[j])
{
++i;
++length;
// If traverse till end
if (i == n)
break;
}
}
// Update maxlen
maxlen = max(maxlen,
length);
}
// Return minimum cost
return n - maxlen;
}
// Driver Code
int main()
{
// Given two strings A and B
string A = "edacb";
string B = "abcde";
// Function call
cout << minCost(A, B) << endl;
}
// This code is contributed by sanjoy_62
Java
// Java Program for the above approach
import java.util.*;
import java.lang.*;
class GFG {
// Function to find the minimum cost
// to convert string A to string B
static int minCost(String A, String B)
{
// Length of string
int n = A.length();
int i = 0;
// Initialize maxlen as 0
int maxlen = 0;
// Traverse the string A
while (i < n) {
// Stores the length of
// substrings of string A
int length = 0;
// Traversing string B for
// each character of A
for (int j = 0; j < n; ++j) {
// Shift i pointer towards
// right and increment length,
// if A[i] equals B[j]
if (A.charAt(i) == B.charAt(j)) {
++i;
++length;
// If traverse till end
if (i == n)
break;
}
}
// Update maxlen
maxlen = Math.max(maxlen,
length);
}
// Return minimum cost
return n - maxlen;
}
// Driver Code
public static void main(String[] args)
{
// Given two strings A and B
String A = "edacb";
String B = "abcde";
// Function call
System.out.println(minCost(A, B));
}
}
Python3
# Python3 Program for # the above approach # Function to find the # minimum cost to convert # string A to string B def minCost(A, B): # Length of string n = len(A); i = 0; # Initialize maxlen as 0 maxlen = 0; # Traverse the string A while (i < n): # Stores the length of # substrings of string A length = 0; # Traversing string B for # each character of A for j in range(0, n): # Shift i pointer towards # right and increment length, # if A[i] equals B[j] if (A[i] == B[j]): i+= 1 length+=1; # If traverse till end if (i == n): break; # Update maxlen maxlen = max(maxlen, length); # Return minimum cost return n - maxlen; # Driver Code if __name__ == '__main__': # Given two strings A and B A = "edacb"; B = "abcde"; # Function call print(minCost(A, B)); # This code is contributed by Rajput-Ji
C#
// C# program for the above approach
using System;
using System.Collections.Generic;
class GFG{
// Function to find the minimum cost
// to convert string A to string B
static int minCost(string A, string B)
{
// Length of string
int n = A.Length;
int i = 0;
// Initialize maxlen as 0
int maxlen = 0;
// Traverse the string A
while (i < n)
{
// Stores the length of
// substrings of string A
int length = 0;
// Traversing string B for
// each character of A
for(int j = 0; j < n; ++j)
{
// Shift i pointer towards
// right and increment length,
// if A[i] equals B[j]
if (A[i] == B[j])
{
++i;
++length;
// If traverse till end
if (i == n)
break;
}
}
// Update maxlen
maxlen = Math.Max(maxlen,
length);
}
// Return minimum cost
return n - maxlen;
}
// Driver Code
public static void Main()
{
// Given two strings A and B
string A = "edacb";
string B = "abcde";
// Function call
Console.WriteLine(minCost(A, B));
}
}
// This code is contributed by sanjoy_62
Javascript
<script>
// Javascript program for the above approach
// Function to find the minimum cost
// to convert string A to string B
function minCost(A, B)
{
// Length of string
var n = A.length;
var i = 0;
// Initialize maxlen as 0
var maxlen = 0;
// Traverse the string A
while (i < n)
{
// Stores the length of
// substrings of string A
var length = 0;
// Traversing string B for
// each character of A
for(var j = 0; j < n; ++j)
{
// Shift i pointer towards
// right and increment length,
// if A[i] equals B[j]
if (A[i] == B[j])
{
++i;
++length;
// If traverse till end
if (i == n)
break;
}
}
// Update maxlen
maxlen = Math.max(maxlen,
length);
}
// Return minimum cost
return n - maxlen;
}
// Driver Code
// Given two strings A and B
var A = "edacb";
var B = "abcde";
// Function call
document.write(minCost(A, B));
// This code is contributed by itsok.
</script>
3
Complejidad de tiempo: O(N 2 ), donde N es la longitud de las strings
Espacio auxiliar: O(N)