Cuente el intercambio mínimo para hacer un palíndromo de cuerdas

Dada una string S, la tarea es encontrar el número mínimo de intercambios adyacentes requeridos para hacer palíndromo de string. Si no es posible, devuelva -1 .

Ejemplos:

Entrada: aabcb 
Salida: 3 
Explicación: 
Después del 1er intercambio: abacb 
Después del 2do intercambio: abcab 
Después del 3er intercambio: abcba

Entrada: adbcdbad 
Salida: -1 

Enfoque
Los siguientes son pasos detallados para resolver este problema. 

• Compruebe si es posible hacer un palíndromo o no a partir de la string dada. Como sabemos, si más de un carácter en una string aparece un número impar de veces, esa string no puede ser un palíndromo. 
• Si el palíndromo no es posible, devuelve -1 .
• Tome dos punteros a la izquierda que apunten al índice 0 y un puntero a la derecha que apunte al último índice de la string dada
• Haga lo siguiente hasta que el puntero izquierdo sea menor que el puntero derecho :
  • Fije el puntero izquierdo y mueva una copia del puntero derecho, digamos r, al lado derecho para buscar el elemento que es similar al carácter que señala el puntero izquierdo .
  • Si el puntero izquierdo es igual al puntero r , significa que este es un carácter extraño que tenemos que mover en el medio de la string.
    •  Así que cambie el carácter en el índice r a su siguiente índice (mueva el carácter hacia el lado derecho)
    • Incremente el resultado en 1 para esta operación de intercambio.
  • De lo contrario,
    • Cambie el carácter encontrado en r al lado derecho, hasta que llegue al índice derecho y siga incrementando el resultado de la operación de intercambio.
    • Incrementa a la izquierda en 1 y disminuye a la derecha en 1.
• Devuelve el resultado.

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

#include <bits/stdc++.h>
using namespace std;
 
int minSwap(string s)
{
    unordered_map<char, int> unmp;
    int odd = 0, left = 0, right = s.size() - 1, result = 0;
 
    for (char ch : s)
        unmp[ch]++;
 
    for (auto i : unmp)
        if (i.second % 2 == 1)
            odd++;
 
    if (odd > 1)
        return -1;
 
    while (left < right) {
        int l = left, r = right;
        while (s[l] != s[r])
            r--;
        if (l == r) {
 
            // when we found odd element
            swap(s[r], s[r + 1]);
            result++;
            continue;
        }
        else {
            // Normal element
            while (r < right) {
                swap(s[r], s[r + 1]);
                result++;
                r++;
            }
        }
        left++, right--;
    }
    return result;
}
 
// Driver's code
int main()
{
    string s = "aabcc";
    cout << minSwap(s);
    return 0;
}

4

Tiempo Complejidad: O(n ² ) 
Espacio Auxiliar: O(1)