Dada una string S que consta de N caracteres, la tarea es modificar la string S realizando el número mínimo de operaciones siguientes de modo que la string S modificada sea la concatenación de su mitad.
- Inserte cualquier carácter nuevo en cualquier índice de la string.
- Elimina cualquier carácter de la string S .
- Reemplace cualquier carácter con cualquier otro carácter en la string S .
Ejemplos:
Entrada: S = “aabbaabb”
Salida: 0
Explicación:
La string dada S = “aabbaabb” tiene la forma A = B + B, donde B = “aabb”. Por lo tanto, el número mínimo de operaciones requeridas es 0.Entrada: S = “aba”
Salida: 1
Enfoque: el problema dado se puede resolver recorriendo la string dada y realizando las operaciones dadas en todos los índices posibles de forma recursiva y luego encontrar las operaciones mínimas requeridas después de atravesar la string. Siga los pasos a continuación para resolver el problema dado:
- Inicialice una variable, digamos minSteps como INT_MAX que almacena la cantidad mínima de operaciones requeridas.
- Recorra la string S dada usando la variable i y realice los siguientes pasos:
- Encuentre las substrings S1 como S[0, i] y S2 como S[i, N] .
- Ahora busque el número mínimo de pasos requeridos para convertir S1 en S2 y almacénelo en el conteo de variables usando el enfoque discutido en este artículo ya que las operaciones son similares a las de este artículo .
- Actualice el valor de minSteps al mínimo de minSteps y cuente .
- Después de completar los pasos anteriores, imprima el valor de minSteps como la operación mínima resultante.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
// Function to find the minimum of
// the three numbers
int getMin(int x, int y, int z)
{
return min(min(x, y), z);
}
// Function to find the minimum number
// operations required to convert string
// str1 to str2 using the operations
int editDistance(string str1, string str2,
int m, int n)
{
// Stores the results of subproblems
int dp[m + 1][n + 1];
// Fill dp[][] in bottom up manner
for (int i = 0; i <= m; i++) {
for (int j = 0; j <= n; j++) {
// If str1 is empty, then
// insert all characters
// of string str2
if (i == 0)
// Minimum operations
// is j
dp[i][j] = j;
// If str2 is empty, then
// remove all characters
// of string str2
else if (j == 0)
// Minimum operations
// is i
dp[i][j] = i;
// If the last characters
// are same, then ignore
// last character
else if (str1[i - 1] == str2[j - 1])
dp[i][j] = dp[i - 1][j - 1];
// If the last character
// is different, then
// find the minimum
else {
// Perform one of the
// insert, remove and
// the replace
dp[i][j] = 1
+ getMin(
dp[i][j - 1],
dp[i - 1][j],
dp[i - 1][j - 1]);
}
}
}
// Return the minimum number of
// steps required
return dp[m][n];
}
// Function to find the minimum number
// of steps to modify the string such
// that first half and second half
// becomes the same
void minimumSteps(string& S, int N)
{
// Stores the minimum number of
// operations required
int ans = INT_MAX;
// Traverse the given string S
for (int i = 1; i < N; i++) {
string S1 = S.substr(0, i);
string S2 = S.substr(i);
// Find the minimum operations
int count = editDistance(
S1, S2, S1.length(),
S2.length());
// Update the ans
ans = min(ans, count);
}
// Print the result
cout << ans << '\n';
}
// Driver Code
int main()
{
string S = "aabb";
int N = S.length();
minimumSteps(S, N);
return 0;
}
Java
// Java program for the above approach
class GFG
{
// Function to find the minimum of
// the three numbers
static int getMin(int x, int y, int z)
{
return Math.min(Math.min(x, y), z);
}
// Function to find the minimum number
// operations required to convert String
// str1 to str2 using the operations
static int editDistance(String str1, String str2,
int m, int n)
{
// Stores the results of subproblems
int [][]dp = new int[m + 1][n + 1];
// Fill dp[][] in bottom up manner
for (int i = 0; i <= m; i++)
{
for (int j = 0; j <= n; j++)
{
// If str1 is empty, then
// insert all characters
// of String str2
if (i == 0)
// Minimum operations
// is j
dp[i][j] = j;
// If str2 is empty, then
// remove all characters
// of String str2
else if (j == 0)
// Minimum operations
// is i
dp[i][j] = i;
// If the last characters
// are same, then ignore
// last character
else if (str1.charAt(i - 1) == str2.charAt(j - 1))
dp[i][j] = dp[i - 1][j - 1];
// If the last character
// is different, then
// find the minimum
else {
// Perform one of the
// insert, remove and
// the replace
dp[i][j] = 1
+ getMin(
dp[i][j - 1],
dp[i - 1][j],
dp[i - 1][j - 1]);
}
}
}
// Return the minimum number of
// steps required
return dp[m][n];
}
// Function to find the minimum number
// of steps to modify the String such
// that first half and second half
// becomes the same
static void minimumSteps(String S, int N)
{
// Stores the minimum number of
// operations required
int ans = Integer.MAX_VALUE;
// Traverse the given String S
for (int i = 1; i < N; i++) {
String S1 = S.substring(0, i);
String S2 = S.substring(i);
// Find the minimum operations
int count = editDistance(
S1, S2, S1.length(),
S2.length());
// Update the ans
ans = Math.min(ans, count);
}
// Print the result
System.out.print(ans);
}
// Driver Code
public static void main(String[] args)
{
String S = "aabb";
int N = S.length();
minimumSteps(S, N);
}
}
// This code is contributed by 29AjayKumar
Python3
# Python program for the above approach; # Function to find the minimum of # the three numbers def getMin(x, y, z): return min(min(x, y), z) # Function to find the minimum number # operations required to convert string # str1 to str2 using the operations def editDistance(str1, str2, m, n): # Stores the results of subproblems dp = [[0 for i in range(n + 1)] for j in range(m + 1)] # Fill dp[][] in bottom up manner for i in range(0, m + 1): for j in range(0, n + 1): # If str1 is empty, then # insert all characters # of string str2 if (i == 0): # Minimum operations # is j dp[i][j] = j # If str2 is empty, then # remove all characters # of string str2 elif (j == 0): # Minimum operations # is i dp[i][j] = i # If the last characters # are same, then ignore # last character elif (str1[i - 1] == str2[j - 1]): dp[i][j] = dp[i - 1][j - 1] # If the last character # is different, then # find the minimum else: # Perform one of the # insert, remove and # the replace dp[i][j] = 1 + getMin( dp[i][j - 1], dp[i - 1][j], dp[i - 1][j - 1]) # Return the minimum number of # steps required return dp[m][n] # Function to find the minimum number # of steps to modify the string such # that first half and second half # becomes the same def minimumSteps(S, N): # Stores the minimum number of # operations required ans = 10**10 # Traverse the given string S for i in range(1, N): S1 = S[:i] S2 = S[i:] # Find the minimum operations count = editDistance(S1, S2, len(S1), len(S2)) # Update the ans ans = min(ans, count) # Print the result print(ans) # Driver Code S = "aabb" N = len(S) minimumSteps(S, N) # This code is contributed by gfgking
C#
// C# program for the above approach
using System;
public class GFG
{
// Function to find the minimum of
// the three numbers
static int getMin(int x, int y, int z)
{
return Math.Min(Math.Min(x, y), z);
}
// Function to find the minimum number
// operations required to convert String
// str1 to str2 using the operations
static int editDistance(string str1, string str2,
int m, int n)
{
// Stores the results of subproblems
int [,]dp = new int[m + 1,n + 1];
// Fill dp[,] in bottom up manner
for (int i = 0; i <= m; i++)
{
for (int j = 0; j <= n; j++)
{
// If str1 is empty, then
// insert all characters
// of String str2
if (i == 0)
// Minimum operations
// is j
dp[i,j] = j;
// If str2 is empty, then
// remove all characters
// of String str2
else if (j == 0)
// Minimum operations
// is i
dp[i,j] = i;
// If the last characters
// are same, then ignore
// last character
else if (str1[i - 1] == str2[j - 1])
dp[i,j] = dp[i - 1,j - 1];
// If the last character
// is different, then
// find the minimum
else {
// Perform one of the
// insert, remove and
// the replace
dp[i,j] = 1
+ getMin(
dp[i,j - 1],
dp[i - 1,j],
dp[i - 1,j - 1]);
}
}
}
// Return the minimum number of
// steps required
return dp[m,n];
}
// Function to find the minimum number
// of steps to modify the String such
// that first half and second half
// becomes the same
static void minimumSteps(string S, int N)
{
// Stores the minimum number of
// operations required
int ans = int.MaxValue;
// Traverse the given String S
for (int i = 1; i < N; i++) {
string S1 = S.Substring(0, i);
string S2 = S.Substring(i);
// Find the minimum operations
int count = editDistance(
S1, S2, S1.Length,
S2.Length);
// Update the ans
ans = Math.Min(ans, count);
}
// Print the result
Console.Write(ans);
}
// Driver Code
public static void Main(string[] args)
{
string S = "aabb";
int N = S.Length;
minimumSteps(S, N);
}
}
// This code is contributed by AnkThon
Javascript
<script>
// JavaScript program for the above approach;
// Function to find the minimum of
// the three numbers
function getMin(x, y, z) {
return Math.min(Math.min(x, y), z);
}
// Function to find the minimum number
// operations required to convert string
// str1 to str2 using the operations
function editDistance(str1, str2, m, n)
{
// Stores the results of subproblems
let dp = new Array(m + 1).fill(new Array(n + 1));
// Fill dp[][] in bottom up manner
for (let i = 0; i <= m; i++) {
for (let j = 0; j <= n; j++) {
// If str1 is empty, then
// insert all characters
// of string str2
if (i == 0)
// Minimum operations
// is j
dp[i][j] = j;
// If str2 is empty, then
// remove all characters
// of string str2
else if (j == 0)
// Minimum operations
// is i
dp[i][j] = i;
// If the last characters
// are same, then ignore
// last character
else if (str1[i - 1] == str2[j - 1])
dp[i][j] = dp[i - 1][j - 1];
// If the last character
// is different, then
// find the minimum
else {
// Perform one of the
// insert, remove and
// the replace
dp[i][j] = 1
+ getMin(
dp[i][j - 1],
dp[i - 1][j],
dp[i - 1][j - 1]);
}
}
}
// Return the minimum number of
// steps required
return dp[m][n];
}
// Function to find the minimum number
// of steps to modify the string such
// that first half and second half
// becomes the same
function minimumSteps(S, N) {
// Stores the minimum number of
// operations required
let ans = Number.MAX_VALUE;
// Traverse the given string S
for (let i = 1; i < N; i++) {
let S1 = S.substring(0, i);
let S2 = S.substring(i);
// Find the minimum operations
let count = editDistance(
S1, S2, S1.length,
S2.length);
// Update the ans
ans = Math.min(ans, count);
}
// Print the result
document.write(ans - 1);
}
// Driver Code
let S = "aabb";
let N = S.length;
minimumSteps(S, N);
// This code is contributed by Potta Lokesh
</script>
Producción:
2
Complejidad de Tiempo: O(N 3 )
Espacio Auxiliar: O(N 2 )
Publicación traducida automáticamente
Artículo escrito por sohailahmed46khan786 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA