Minimice los intercambios de pares de caracteres necesarios de modo que no haya dos caracteres adyacentes en la string que sean iguales

Dada una string S que consta de N caracteres, la tarea es encontrar el número mínimo de pares de caracteres que se requieren intercambiar de manera que no haya dos caracteres adyacentes iguales. Si no es posible hacerlo, imprima “-1” .

Ejemplos:

Entrada: S = “ABAACD”
Salida: 1
Explicación: Intercambiar S[3] y S[4] modifica la string dada S a “ABACAD”. Dado que no hay dos caracteres adyacentes iguales, el número mínimo de operaciones requeridas es 1.

Entrada: S = “AABA”
Salida: -1

Enfoque: El problema dado se puede resolver usando Backtracking . La idea es generar todas las combinaciones posibles de intercambio de un par de índices y luego, si la string se genera sin caracteres adyacentes, igual con el intercambio mínimo, luego imprima ese número mínimo de operaciones de intercambio realizadas. Siga los pasos a continuación para resolver el problema:

• Defina una función minimalSwaps(string &str, int &minimumSwaps, int swaps=0, int idx) y realice las siguientes operaciones:
  • Si los caracteres adyacentes de la string str son diferentes, actualice el valor de los cambios mínimos al mínimo de cambios mínimos e intercambios .
  • Iterar sobre el rango [idx, N] usando la variable i y realizando las siguientes operaciones:
    • Iterar sobre el rango [i + 1, N] usando la variable j y realizando las siguientes operaciones:
      • Intercambie los caracteres en las posiciones i y j en la string S .
      • Llame a la función de intercambios mínimos (str, intercambios mínimos, intercambios + 1, i + 1) para encontrar otros posibles pares de intercambio para generar la string resultante.
      • Intercambie los caracteres en las posiciones i y j en la string S .
• Inicialice la variable, digamos ansSwaps como INT_MAX para almacenar el recuento de intercambios mínimos requeridos.
• Llame a la función minimalSwaps(str, ansSwaps) para encontrar el número mínimo de intercambios necesarios para que todos los caracteres adyacentes sean diferentes.
• Después de completar los pasos anteriores, si el valor de ansSwaps es INT_MAX, imprima -1 . De lo contrario, imprima el valor de ansSwaps como los swaps mínimos resultantes.

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 check if S
// contains any pair of
// adjacent characters that are same
bool check(string& S)
{
    // Traverse the string S
    for (int i = 1; i < S.length(); i++) {
 
        // If current pair of adjacent
        // characters are the same
        if (S[i - 1] == S[i]) {
            return false;
        }
    }
 
    // Return true
    return true;
}
 
// Utility function to find the minimum number
// of swaps of pair of characters required
// to make all pairs of adjacent characters different
void minimumSwaps(string& S, int& ansSwaps,
                  int swaps = 0, int idx = 0)
{
    // Check if the required string
    // is formed already
    if (check(S)) {
        ansSwaps = min(ansSwaps, swaps);
    }
 
    // Traverse the string S
    for (int i = idx;
         i < S.length(); i++) {
 
        for (int j = i + 1;
             j < S.length(); j++) {
 
            // Swap the characters at i
            // and j position
            swap(S[i], S[j]);
            minimumSwaps(S, ansSwaps,
                         swaps + 1, i + 1);
 
            // Swap for Backtracking
            // Step
            swap(S[i], S[j]);
        }
    }
}
 
// Function to find the minimum number
// of swaps of pair of characters required
// to make all pairs of adjacent characters different
void findMinimumSwaps(string& S)
{
 
    // Stores the resultant minimum
    // number of swaps required
    int ansSwaps = INT_MAX;
 
    // Function call to find the
    // minimum swaps required
    minimumSwaps(S, ansSwaps);
 
    // Print the result
    if (ansSwaps == INT_MAX)
        cout << "-1";
    else
        cout << ansSwaps;
}
 
// Driver Code
int main()
{
    string S = "ABAACD";
    findMinimumSwaps(S);
 
    return 0;
}

// Java program for the above approach
import java.util.*;
 
class GFG
{
    static int ansSwaps ;
   
// Function to check if S
// contains any pair of
// adjacent characters that are same
static boolean check(char[] S)
{
   
    // Traverse the String S
    for (int i = 1; i < S.length; i++) {
 
        // If current pair of adjacent
        // characters are the same
        if (S[i - 1] == S[i]) {
            return false;
        }
    }
 
    // Return true
    return true;
}
 
// Utility function to find the minimum number
// of swaps of pair of characters required
// to make all pairs of adjacent characters different
static void minimumSwaps(char[] S,
                  int swaps, int idx)
{
   
    // Check if the required String
    // is formed already
    if (check(S)) {
        ansSwaps = Math.min(ansSwaps, swaps);
    }
 
    // Traverse the String S
    for (int i = idx;
         i < S.length; i++) {
 
        for (int j = i + 1;
             j < S.length; j++) {
 
            // Swap the characters at i
            // and j position
            swap(S,i,j);
            minimumSwaps(S,
                         swaps + 1, i + 1);
 
            // Swap for Backtracking
            // Step
            S= swap(S,i,j);
        }
    }
}
static char[] swap(char []arr, int i, int j){
    char temp= arr[i];
    arr[i]=arr[j];
    arr[j]=temp;
    return arr;
}
   
// Function to find the minimum number
// of swaps of pair of characters required
// to make all pairs of adjacent characters different
static void findMinimumSwaps(char[] S)
{
 
    // Stores the resultant minimum
    // number of swaps required
    ansSwaps = Integer.MAX_VALUE;
 
    // Function call to find the
    // minimum swaps required
    minimumSwaps(S, 0,0);
 
    // Print the result
    if (ansSwaps == Integer.MAX_VALUE)
        System.out.print("-1");
    else
        System.out.print(ansSwaps);
}
 
// Driver Code
public static void main(String[] args)
{
    String S = "ABAACD";
    findMinimumSwaps(S.toCharArray());
 
}
}
 
// This code is contributed by 29AjayKumar

# Python3 program for the above approach
import sys
ansSwaps = 0
 
# Function to check if S
# contains any pair of
# adjacent characters that are same
def check(S):
   
    # Traverse the String S
    for i in range(1, len(S)):
       
        # If current pair of adjacent
        # characters are the same
        if (S[i - 1] == S[i]):
            return False
  
    # Return true
    return True
  
# Utility function to find the minimum number
# of swaps of pair of characters required
# to make all pairs of adjacent characters different
def minimumSwaps(S, swaps , idx):
    global ansSwaps
     
    # Check if the required String
    # is formed already
    if (check(S)):
        ansSwaps = 1+min(ansSwaps, swaps)
  
    # Traverse the String S
    for i in range(idx, len(S)):
        for j in range(i + 1, len(S)):
           
            # Swap the characters at i
            # and j position
            swap(S, i, j)
            minimumSwaps(S, swaps + 1, i + 1)
  
            # Swap for Backtracking
            # Step
            S = swap(S, i, j)
  
def swap(arr , i , j):
    temp = arr[i]
    arr[i] = arr[j]
    arr[j] = temp
    return arr
    
# Function to find the minimum number
# of swaps of pair of characters required
# to make all pairs of adjacent characters different
def findMinimumSwaps(S):
    global ansSwaps
     
    # Stores the resultant minimum
    # number of swaps required
    ansSwaps = sys.maxsize
  
    # Function call to find the
    # minimum swaps required
    minimumSwaps(S, 0,0)
  
    # Print the result
    if (ansSwaps == sys.maxsize):
        print("-1")
    else:
        print(ansSwaps)
 
S = "ABAACD"
findMinimumSwaps(S.split())
 
# This code is contributed by rameshtravel07.

// C# program for the above approach
using System;
 
public class GFG
{
    static int ansSwaps ;
   
// Function to check if S
// contains any pair of
// adjacent characters that are same
static bool check(char[] S)
{
   
    // Traverse the String S
    for (int i = 1; i < S.Length; i++) {
 
        // If current pair of adjacent
        // characters are the same
        if (S[i - 1] == S[i]) {
            return false;
        }
    }
 
    // Return true
    return true;
}
 
// Utility function to find the minimum number
// of swaps of pair of characters required
// to make all pairs of adjacent characters different
static void minimumSwaps(char[] S,
                  int swaps, int idx)
{
   
    // Check if the required String
    // is formed already
    if (check(S)) {
        ansSwaps = Math.Min(ansSwaps, swaps);
    }
 
    // Traverse the String S
    for (int i = idx;
         i < S.Length; i++) {
 
        for (int j = i + 1;
             j < S.Length; j++) {
 
            // Swap the characters at i
            // and j position
            swap(S,i,j);
            minimumSwaps(S,
                         swaps + 1, i + 1);
 
            // Swap for Backtracking
            // Step
            S= swap(S,i,j);
        }
    }
}
static char[] swap(char []arr, int i, int j){
    char temp= arr[i];
    arr[i]=arr[j];
    arr[j]=temp;
    return arr;
}
   
// Function to find the minimum number
// of swaps of pair of characters required
// to make all pairs of adjacent characters different
static void findMinimumSwaps(char[] S)
{
 
    // Stores the resultant minimum
    // number of swaps required
    ansSwaps = int.MaxValue;
 
    // Function call to find the
    // minimum swaps required
    minimumSwaps(S, 0,0);
 
    // Print the result
    if (ansSwaps == int.MaxValue)
        Console.Write("-1");
    else
        Console.Write(ansSwaps);
}
 
// Driver Code
public static void Main(String[] args)
{
    String S = "ABAACD";
    findMinimumSwaps(S.ToCharArray());
 
}
}
 
// This code is contributed by 29AjayKumar.

<script>
 
// javascript program for the above approach
var ansSwaps ;
   
// Function to check if S
// contains any pair of
// adjacent characters that are same
function check(S)
{
   
    // Traverse the String S
    for (var i = 1; i < S.length; i++) {
 
        // If current pair of adjacent
        // characters are the same
        if (S[i - 1] == S[i]) {
            return false;
        }
    }
 
    // Return true
    return true;
}
 
// Utility function to find the minimum number
// of swaps of pair of characters required
// to make all pairs of adjacent characters different
function minimumSwaps(S, swaps , idx)
{
   
    // Check if the required String
    // is formed already
    if (check(S)) {
        ansSwaps = Math.min(ansSwaps, swaps);
    }
 
    // Traverse the String S
    for (var i = idx;
         i < S.length; i++) {
 
        for (var j = i + 1;
             j < S.length; j++) {
 
            // Swap the characters at i
            // and j position
            swap(S,i,j);
            minimumSwaps(S,
                         swaps + 1, i + 1);
 
            // Swap for Backtracking
            // Step
            S= swap(S,i,j);
        }
    }
}
function swap(arr , i , j){
    var temp= arr[i];
    arr[i]=arr[j];
    arr[j]=temp;
    return arr;
}
   
// Function to find the minimum number
// of swaps of pair of characters required
// to make all pairs of adjacent characters different
function findMinimumSwaps(S)
{
 
    // Stores the resultant minimum
    // number of swaps required
    ansSwaps = Number.MAX_VALUE;
 
    // Function call to find the
    // minimum swaps required
    minimumSwaps(S, 0,0);
 
    // Print the result
    if (ansSwaps == Number.MAX_VALUE)
        document.write("-1");
    else
        document.write(ansSwaps);
}
 
// Driver Code
 
    var S = "ABAACD";
    findMinimumSwaps(S.split(''));
 
// This code is contributed by 29AjayKumar
</script>

1

Complejidad de Tiempo: O(N ³ *2 ^N )
Espacio Auxiliar: O(1)