Dada una string s . La tarea es minimizar el número de intercambios adyacentes necesarios para invertir la string.
Ejemplos:
Entrada : s = “abc”
Salida : 3
Explicación : Siga las operaciones a continuación para resolver el problema dado.
intercambio (1, 2) -> «bac»
intercambio (2, 3) -> «bca»
intercambio (1, 2) -> «cba»Entrada : s = “ba”
Salida : 1
Enfoque : este problema se puede resolver comparando la string dada con su reverso y contando el número de intercambios necesarios para formar la string invertida. Siga los pasos a continuación para resolver el problema:
- Inicialice una string s2 como la copia de la string original s .
- string inversa s2
- Inicialice result = 0 para almacenar la cantidad de intercambios adyacentes necesarios para invertir la string.
- Itere usando dos punteros i y j para ambas strings y encuentre cada ocurrencia de s en s2 a través de dos punteros i y j
- Cada vez que establezca resultado = resultado + j – i .
- Devuelve resultado como respuesta final.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program for above approach
#include <bits/stdc++.h>
using namespace std;
// Function to find minimum adjacent swaps
// Required to reverse the string
int min_swaps(string s)
{
string s2 = s;
// Reverse a string
reverse(s2.begin(), s2.end());
int i = 0, j = 0;
int result = 0;
int n = s.length();
while (i < n) {
j = i;
// Iterate till characters
// of both the strings match
while (s[j] != s2[i]) {
j += 1;
}
// Iterating until i=j
// result will be j-i
while (i < j) {
char temp = s[j];
s[j] = s[j - 1];
s[j - 1] = temp;
j -= 1;
result += 1;
}
i += 1;
}
return result;
}
// Driver code
int main()
{
string s = "abc";
cout << min_swaps(s);
return 0;
}
Java
// Java program for above approach
public class GFG {
static int min_swaps(String s)
{
String s2 = "";
// Reverse a string
char[] cArray = s.toCharArray();
for (int k = cArray.length - 1; k > -1; k--) {
s2 += cArray[k];
}
int i = 0, j = 0;
int result = 0;
int n = s.length();
while (i < n) {
j = i;
// Iterate till characters
// of both the strings match
while (s.charAt(j) != s2.charAt(i)) {
j += 1;
}
// Iterating until i=j
// result will be j-i
while (i < j) {
char temp = s.charAt(j);
char[] ch = s.toCharArray();
ch[j] = ch[j - 1];
ch[j - 1] = temp;
s = new String(ch);
j -= 1;
result += 1;
}
i += 1;
}
return result;
}
// Driver code
static public void main(String []args)
{
String s = "abc";
System.out.println(min_swaps(s));
}
}
// This code is contributed by AnkThon
Python3
# python program for above approach # Function to find minimum adjacent swaps # Required to reverse the string def min_swaps(s): s2 = s.copy() # Reverse a string s2.reverse() i = 0 j = 0 result = 0 n = len(s) while (i < n): j = i # Iterate till characters # of both the strings match while (s[j] != s2[i]): j += 1 # Iterating until i=j # result will be j-i while (i < j): temp = s[j] s[j] = s[j - 1] s[j - 1] = temp j -= 1 result += 1 i += 1 return result # Driver code if __name__ == "__main__": s = "abc" s = list(s) print(min_swaps(s)) # This code is contributed by rakeshsahni
C#
using System;
public class GFG {
static int min_swaps(string s)
{
string s2 = String.Empty;
// Reverse a string
char[] cArray = s.ToCharArray();
for (int k = cArray.Length - 1; k > -1; k--) {
s2 += cArray[k];
}
int i = 0, j = 0;
int result = 0;
int n = s.Length;
while (i < n) {
j = i;
// Iterate till characters
// of both the strings match
while (s[j] != s2[i]) {
j += 1;
}
// Iterating until i=j
// result will be j-i
while (i < j) {
char temp = s[j];
char[] ch = s.ToCharArray();
ch[j] = ch[j - 1];
ch[j - 1] = temp;
s = new string(ch);
j -= 1;
result += 1;
}
i += 1;
}
return result;
}
// Driver code
static public void Main()
{
string s = "abc";
Console.WriteLine(min_swaps(s));
}
}
// This code is contributed by maddler.
Javascript
<script>
// Javascript program for above approach
// Function to find minimum adjacent swaps
// Required to reverse the string
function min_swaps(s)
{
var s2 = JSON.parse(JSON.stringify(s));
s = s.split('');
s2 = s2.split('');
// Reverse a string
s2.reverse();
var i = 0, j = 0;
var result = 0;
var n = s.length;
while (i < n) {
j = i;
// Iterate till characters
// of both the strings match
while (s[j] != s2[i]) {
j += 1;
}
// Iterating until i=j
// result will be j-i
while (i < j) {
var temp = s[j];
s[j] = s[j - 1];
s[j - 1] = temp;
j -= 1;
result += 1;
}
i += 1;
}
return result;
}
// Driver code
var s = "abc";
document.write(min_swaps(s));
// This code is contributed by rutvik_56.
</script>
Producción:
3
Complejidad de tiempo : O (N 2 ), donde N es el tamaño de la string dada.
Espacio Auxiliar : O(1).
Publicación traducida automáticamente
Artículo escrito por sallagondaavinashreddy7 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA