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 .
- Iterar sobre el rango [i + 1, N] usando la variable j y realizando las siguientes operaciones:
- 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++
// 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
// 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
# 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#
// 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.
Javascript
<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>
Producción:
1
Complejidad de Tiempo: O(N 3 *2 N )
Espacio Auxiliar: O(1)
Publicación traducida automáticamente
Artículo escrito por Paras Saini y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA