Dadas dos strings s1 y s2 , la tarea es encontrar el número mínimo de pasos necesarios para convertir s1 en s2 . La única operación permitida es intercambiar elementos adyacentes en la primera string. Cada intercambio se cuenta como un solo paso.
Ejemplos:
Entrada: s1 = “abcd”, s2 = “cdab”
Salida: 4
Intercambiar 2 ° y 3 ° elemento, abcd => acbd
Intercambiar 1 ° y 2 ° elemento, acbd => cabd
Intercambiar 3 ° y 4 ° elemento, cabd = > cadb
Intercambiar 2º y 3er elemento , cadb => cdab
Se requiere un mínimo de 4 intercambios.
Entrada: s1 = “abcfdegji”, s2 = “fjiacbdge”
Salida: 17
Enfoque: Use dos punteros i y j para la primera y segunda string respectivamente. Inicialice i y j a 0 .
Iterar sobre la primera string y encontrar la posición j tal que s1[j] = s2[i] incrementando el valor a j . Continúe intercambiando los elementos adyacentes j y j – 1 y disminuya j hasta que sea mayor que i .
Ahora el i -ésimo elemento de la primera string es igual a la segunda string, por lo tanto, incrementa el valor de i .
Esta técnica dará la cantidad mínima de pasos ya que no hay intercambios innecesarios.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ implementation of the above approach
#include <bits/stdc++.h>
using namespace std;
// Function that returns true if s1
// and s2 are anagrams of each other
bool isAnagram(string s1, string s2)
{
sort(s1.begin(), s1.end());
sort(s2.begin(), s2.end());
if (s1 == s2)
return 1;
return 0;
}
// Function to return the minimum swaps required
int CountSteps(string s1, string s2, int size)
{
int i = 0, j = 0;
int result = 0;
// Iterate over the first string and convert
// every element equal to the second string
while (i < size) {
j = i;
// Find index element of first string which
// is equal to the ith element of second string
while (s1[j] != s2[i]) {
j += 1;
}
// Swap adjacent elements in first string so
// that element at ith position becomes equal
while (i < j) {
// Swap elements using temporary variable
char temp = s1[j];
s1[j] = s1[j - 1];
s1[j - 1] = temp;
j -= 1;
result += 1;
}
i += 1;
}
return result;
}
// Driver code
int main()
{
string s1 = "abcd";
string s2 = "cdab";
int size = s2.size();
// If both the strings are anagrams
// of each other then only they
// can be made equal
if (isAnagram(s1, s2))
cout << CountSteps(s1, s2, size);
else
cout << -1;
return 0;
}
Java
// Java implementation of the above approach
import java.util.*;
class GFG
{
// Function that returns true if s1
// and s2 are anagrams of each other
static boolean isAnagram(String s1, String s2)
{
s1 = sortString(s1);
s2 = sortString(s2);
return (s1.equals(s2));
}
// Method to sort a string alphabetically
public static String sortString(String inputString)
{
// convert input string to char array
char tempArray[] = inputString.toCharArray();
// sort tempArray
Arrays.sort(tempArray);
// return new sorted string
return new String(tempArray);
}
// Function to return the minimum swaps required
static int CountSteps(char []s1, char[] s2, int size)
{
int i = 0, j = 0;
int result = 0;
// Iterate over the first string and convert
// every element equal to the second string
while (i < size)
{
j = i;
// Find index element of first string which
// is equal to the ith element of second string
while (s1[j] != s2[i])
{
j += 1;
}
// Swap adjacent elements in first string so
// that element at ith position becomes equal
while (i < j)
{
// Swap elements using temporary variable
char temp = s1[j];
s1[j] = s1[j - 1];
s1[j - 1] = temp;
j -= 1;
result += 1;
}
i += 1;
}
return result;
}
// Driver code
public static void main(String[] args)
{
String s1 = "abcd";
String s2 = "cdab";
int size = s2.length();
// If both the strings are anagrams
// of each other then only they
// can be made equal
if (isAnagram(s1, s2))
System.out.println(CountSteps(s1.toCharArray(), s2.toCharArray(), size));
else
System.out.println(-1);
}
}
// This code is contributed by Rajput-Ji
Python3
# Python3 implementation of the above approach # Function that returns true if s1 # and s2 are anagrams of each other def isAnagram(s1, s2) : s1 = list(s1); s2 = list(s2); s1 = s1.sort(); s2 = s2.sort(); if (s1 == s2) : return 1; return 0; # Function to return the minimum swaps required def CountSteps(s1, s2, size) : s1 = list(s1); s2 = list(s2); i = 0; j = 0; result = 0; # Iterate over the first string and convert # every element equal to the second string while (i < size) : j = i; # Find index element of first string which # is equal to the ith element of second string while (s1[j] != s2[i]) : j += 1; # Swap adjacent elements in first string so # that element at ith position becomes equal while (i < j) : # Swap elements using temporary variable temp = s1[j]; s1[j] = s1[j - 1]; s1[j - 1] = temp; j -= 1; result += 1; i += 1; return result; # Driver code if __name__ == "__main__": s1 = "abcd"; s2 = "cdab"; size = len(s2); # If both the strings are anagrams # of each other then only they # can be made equal if (isAnagram(s1, s2)) : print(CountSteps(s1, s2, size)); else : print(-1); # This code is contributed by AnkitRai01
C#
// C# implementation of the above approach
using System;
using System.Linq;
class GFG
{
// Function that returns true if s1
// and s2 are anagrams of each other
static Boolean isAnagram(String s1, String s2)
{
s1 = sortString(s1);
s2 = sortString(s2);
return (s1.Equals(s2));
}
// Method to sort a string alphabetically
public static String sortString(String inputString)
{
// convert input string to char array
char []tempArray = inputString.ToCharArray();
// sort tempArray
Array.Sort(tempArray);
// return new sorted string
return new String(tempArray);
}
// Function to return the minimum swaps required
static int CountSteps(char []s1, char[] s2, int size)
{
int i = 0, j = 0;
int result = 0;
// Iterate over the first string and convert
// every element equal to the second string
while (i < size)
{
j = i;
// Find index element of first string which
// is equal to the ith element of second string
while (s1[j] != s2[i])
{
j += 1;
}
// Swap adjacent elements in first string so
// that element at ith position becomes equal
while (i < j)
{
// Swap elements using temporary variable
char temp = s1[j];
s1[j] = s1[j - 1];
s1[j - 1] = temp;
j -= 1;
result += 1;
}
i += 1;
}
return result;
}
// Driver code
public static void Main(String[] args)
{
String s1 = "abcd";
String s2 = "cdab";
int size = s2.Length;
// If both the strings are anagrams
// of each other then only they
// can be made equal
if (isAnagram(s1, s2))
Console.WriteLine(CountSteps(s1.ToCharArray(), s2.ToCharArray(), size));
else
Console.WriteLine(-1);
}
}
/* This code is contributed by PrinciRaj1992 */
Javascript
<script>
// Javascript implementation of the above approach
// Function that returns true if s1
// and s2 are anagrams of each other
function isAnagram(s1, s2)
{
s1 = sortString(s1);
s2 = sortString(s2);
return (s1 == s2);
}
// Method to sort a string alphabetically
function sortString(inputString)
{
// convert input string to char array
let tempArray = inputString.split('');
// sort tempArray
tempArray.sort();
// return new sorted string
return tempArray.join("");
}
// Function to return the minimum swaps required
function CountSteps(s1, s2, size)
{
let i = 0, j = 0;
let result = 0;
// Iterate over the first string and convert
// every element equal to the second string
while (i < size)
{
j = i;
// Find index element of first string which
// is equal to the ith element of second string
while (s1[j] != s2[i])
{
j += 1;
}
// Swap adjacent elements in first string so
// that element at ith position becomes equal
while (i < j)
{
// Swap elements using temporary variable
let temp = s1[j];
s1[j] = s1[j - 1];
s1[j - 1] = temp;
j -= 1;
result += 1;
}
i += 1;
}
return result;
}
let s1 = "abcd";
let s2 = "cdab";
let size = s2.length;
// If both the strings are anagrams
// of each other then only they
// can be made equal
if (isAnagram(s1, s2))
document.write(CountSteps(s1.split(''), s2.split(''), size) + "</br>");
else
document.write(-1 + "</br>");
</script>
Producción:
4
Complejidad de tiempo: O (N * N), ya que estamos usando bucles anidados para atravesar N * N veces. Donde N es la longitud de la string.
Espacio auxiliar: O(1), ya que no estamos utilizando ningún espacio adicional.