Haga que la string sea lexicográficamente más pequeña y no palindrómica intercambiando un par de caracteres adyacentes

Dada la string str que consta de alfabetos en minúsculas, la tarea es construir la string no palindrómica lexicográficamente más pequeña intercambiando cualquier par de caracteres adyacentes de la string cualquier número de veces. 
Si la string dada no se puede convertir a una string no palindrómica lexicográficamente más pequeña, imprima » -1″ .

Ejemplos:

Entrada: str = “djfbw” 
Salida: bdfjw
Explicación:
Realice las siguientes operaciones de intercambio para obtener la string lexicográficamente más pequeña no palindrómica:
Intercambie ‘b’ y ‘f’, str se convierte en “djbfw”
Intercambie ‘j’ y ‘b’, str se convierte en “dbjfw” Cambia
‘b’ y ‘d’, str se convierte en “bdjfw” Cambia
‘j’ y ‘f’, str se convierte en “bdfjw”.
Ahora “bdfjw” es la string lexicográficamente más pequeña que no es un palíndromo.

Entrada: str[] = “pppppp” 
Salida: -1

Enfoque ingenuo: la idea es generar todas las permutaciones posibles de la string y comprobar si forman palíndromo o no. Imprime la permutación más pequeña entre ellos.

Complejidad temporal: O(N*N!)
Espacio auxiliar: O(N)

Enfoque eficiente: la idea es verificar si lexicográficamente la string más pequeña posible de la string dada es un palíndromo o no. A continuación se muestran los pasos:

1. Para obtener lexicográficamente la string más pequeña, ordene la string dada para organizar los caracteres de la string en orden creciente.
2. Ahora, si la string ordenada es un palíndromo, significa que la string tiene solo un tipo de carácter y no se puede organizar para formar una string que no sea un palíndromo.
3. Si no es un palíndromo, la string ordenada es lexicográficamente la string más pequeña que no es un palíndromo.

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

// C++ program for the above approach
 
#include <bits/stdc++.h>
using namespace std;
 
// Function to find the lexicographically
// smallest string which is non-palindrome
void smallestNonPalindromic(string& s)
{
 
    // Sort the given string
    sort(s.begin(), s.end());
 
    // Store reverse of sorted string
    string reversestring
        = string(s.rbegin(), s.rend());
 
    // Check if the sorted string is
    // palindromic or not
    if (s != reversestring) {
        cout << s;
    }
    else {
        cout << "-1";
    }
}
 
// Driver Code
int main()
{
    // Given string str
    string str = "asmfjdeovnhekfnj";
 
    // Function Call
    smallestNonPalindromic(str);
    return 0;
}

// Java program for the above approach
import java.util.*;
class GFG{
 
// reverse string
static String reverse(String input)
{
  char[] a = input.toCharArray();
  int l, r = a.length - 1;
  for (l = 0; l < r; l++, r--)
  {
    char temp = a[l];
    a[l] = a[r];
    a[r] = temp;
  }
  return String.valueOf(a);
}
 
// Method to sort a string alphabetically
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 find the lexicographically
// smallest String which is non-palindrome
static void smallestNonPalindromic(String s)
{
  // Sort the given String
  s = sortString(s);
 
  // Store reverse of sorted String
  String reverseString = reverse(s);
 
  // Check if the sorted String is
  // palindromic or not
  if (s != reverseString)
  {
    System.out.print(s);
  }
   
  else
  {
    System.out.print("-1");
  }
}
 
// Driver Code
public static void main(String[] args)
{
  // Given String str
  String str = "asmfjdeovnhekfnj";
 
  // Function Call
  smallestNonPalindromic(str);
}
}
 
// This code is contributed by gauravrajput1

# Python3 program for the above approach
 
# Function to find the lexicographically
# smallest string which is non-palindrome
def smallestNonPalindromic(s):
 
    # Sort the given string
    s = sorted(s)
 
    # Store reverse of sorted string
    reversestring = s[::-1]
 
    # Check if the sorted string is
    # palindromic or not
    if (s != reversestring):
        print("".join(s))
    else:
        print("-1")
 
# Driver Code
if __name__ == '__main__':
     
    # Given string str
    str = "asmfjdeovnhekfnj"
 
    # Function call
    smallestNonPalindromic(str)
 
# This code is contributed by mohit kumar 29

// C# program for the above approach
using System;
 
class GFG{
 
// Reverse string
static String reverse(String input)
{
    char[] a = input.ToCharArray();
    int l, r = a.Length - 1;
     
    for(l = 0; l < r; l++, r--)
    {
        char temp = a[l];
        a[l] = a[r];
        a[r] = temp;
    }
    return String.Join("", a);
}
 
// Method to sort a string alphabetically
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 find the lexicographically
// smallest String which is non-palindrome
static void smallestNonPalindromic(String s)
{
     
    // Sort the given String
    s = sortString(s);
     
    // Store reverse of sorted String
    String reverseString = reverse(s);
     
    // Check if the sorted String is
    // palindromic or not
    if (s != reverseString)
    {
        Console.Write(s);
    }
    else
    {
        Console.Write("-1");
    }
}
 
// Driver Code
public static void Main(String[] args)
{
     
    // Given String str
    String str = "asmfjdeovnhekfnj";
     
    // Function call
    smallestNonPalindromic(str);
}
}
 
// This code is contributed by Amit Katiyar

<script>
      // JavaScript program for the above approach
      // Function to find the lexicographically
      // smallest string which is non-palindrome
      function smallestNonPalindromic(s) {
        var newStr = s.split("");
 
        // Sort the given string
        newStr.sort().reverse();
 
        // Store reverse of sorted string
        var reversestring = newStr.reverse().join("");
 
        // Check if the sorted string is
        // palindromic or not
        if (s !== reversestring) {
          document.write(newStr.join(""));
        } else {
          document.write("-1");
        }
      }
 
      // Driver Code
      // Given string str
      var str = "asmfjdeovnhekfnj";
 
      // Function Call
      smallestNonPalindromic(str);
    </script>

adeeffhjjkmnnosv

Complejidad temporal: O(N)
Espacio auxiliar: O(1)