Dada una string, encuentre el número mínimo de intercambios (no necesariamente adyacentes) para convertirla en una string que tenga caracteres similares uno al lado del otro.
Ejemplos:
Entrada: abcb
Salida: 1
Explicación: intercambiar (c, b) para formar abbc o acbb. El número de operaciones de intercambio para esto es 1;
Entrada: abbaacb
0123456
Salida: 2
Explicación: intercambiar el índice 0 con el índice 6 y luego intercambiar el índice 5 con el índice 6.
La idea es considerar todas las permutaciones formadas a partir de cada intercambio entre dos elementos y también sin intercambiar dos elementos.
C++
#include <bits/stdc++.h>
using namespace std;
// checks whether a string has similar characters side by side
bool sameCharAdj(string str)
{
int n = str.length(), i;
set<char> st;
st.insert(str[0]);
for (i = 1; i < n; i++) {
// If similar chars side by side, continue
if (str[i] == str[i - 1])
continue;
// If we have found a char equal to current
// char and does not exist side to it,
// return false
if (st.find(str[i]) != st.end())
return false;
st.insert(str[i]);
}
return true;
}
// counts min swap operations to convert a string
// that has similar characters side by side
int minSwaps(string str, int l, int r, int cnt, int minm)
{
// Base case
if (l == r) {
if (sameCharAdj(str))
return cnt;
else
return INT_MAX;
}
for (int i = l + 1; i <= r; i++) {
swap(str[i], str[l]);
cnt++;
// considering swapping of i and l chars
int x = minSwaps(str, l + 1, r, cnt, minm);
// Backtrack
swap(str[i], str[l]);
cnt--;
// not considering swapping of i and l chars
int y = minSwaps(str, l + 1, r, cnt, minm);
// taking min of above two
minm = min(minm, min(x, y));
}
return minm;
}
// Driver code
int main()
{
string str = "abbaacb";
int n = str.length(), cnt = 0, minm = INT_MAX;
cout << minSwaps(str, 0, n - 1, cnt, minm) << endl;
return 0;
}
Java
import java.util.*;
class GFG {
// checks whether a String has similar characters side by side
static boolean sameJavaharAdj(char str[]) {
int n = str.length, i;
TreeSet<Character> st = new TreeSet<>();
st.add(str[0]);
for (i = 1; i < n; i++) {
// If similar chars side by side, continue
if (str[i] == str[i - 1]) {
continue;
}
// If we have found a char equal to current
// char and does not exist side to it,
// return false
if (st.contains(str[i]) & (str[i] != st.last())) {
return false;
}
st.add(str[i]);
}
return true;
}
// counts min swap operations to convert a String
// that has similar characters side by side
static int minSwaps(char str[], int l, int r, int cnt, int minm) {
// Base case
if (l == r) {
if (sameJavaharAdj(str)) {
return cnt;
} else {
return Integer.MAX_VALUE;
}
}
for (int i = l + 1; i <= r; i++) {
swap(str, i, l);
cnt++;
// considering swapping of i and l chars
int x = minSwaps(str, l + 1, r, cnt, minm);
// Backtrack
swap(str, i, l);
cnt--;
// not considering swapping of i and l chars
int y = minSwaps(str, l + 1, r, cnt, minm);
// taking Math.min of above two
minm = Math.min(minm, Math.min(x, y));
}
return minm;
}
static void swap(char[] arr, int i, int j) {
char temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
// Driver code
public static void main(String[] args) {
String str = "abbaacb";
int n = str.length(), cnt = 0, minm = Integer.MAX_VALUE;
System.out.print(minSwaps(str.toCharArray(), 0, n - 1, cnt, minm));;
}
}
// This code is contributed Rajput-Ji
Python3
# Python3 implementation of the approach from sys import maxsize # checks whether a string has # similar characters side by side def sameCharAdj(string): n = len(string) st = set() st.add(string[0]) for i in range(1, n): # If similar chars side by side, continue if string[i] == string[i - 1]: continue # If we have found a char equal to current # char and does not exist side to it, # return false if string[i] in st: return False st.add(string[i]) return True # counts min swap operations to convert a string # that has similar characters side by side def minSwaps(string, l, r, cnt, minm): # Base case if l == r: if sameCharAdj(string): return cnt else: return maxsize for i in range(l + 1, r + 1, 1): string[i], string[l] = string[l], string[i] cnt += 1 # considering swapping of i and l chars x = minSwaps(string, l + 1, r, cnt, minm) # Backtrack string[i], string[l] = string[l], string[i] cnt -= 1 # not considering swapping of i and l chars y = minSwaps(string, l + 1, r, cnt, minm) # taking min of above two minm = min(minm, min(x, y)) return minm # Driver Code if __name__ == "__main__": string = "abbaacb" string = list(string) n = len(string) cnt = 0 minm = maxsize print(minSwaps(string, 0, n - 1, cnt, minm)) # This code is contributed by # sanjeev2552
C#
using System;
using System.Collections.Generic;
class GFG
{
// checks whether a String has similar
// characters side by side
static bool sameJavaharAdj(char []str)
{
int n = str.Length, i;
HashSet<char> st = new HashSet<char>();
st.Add(str[0]);
for (i = 1; i < n; i++)
{
// If similar chars side by side, continue
if (str[i] == str[i - 1])
{
continue;
}
// If we have found a char equal to current
// char and does not exist side to it,
// return false
if (st.Contains(str[i]) & !st.Equals(str[i]))
{
return false;
}
st.Add(str[i]);
}
return true;
}
// counts min swap operations to convert a String
// that has similar characters side by side
static int minSwaps(char []str, int l, int r,
int cnt, int minm)
{
// Base case
if (l == r)
{
if (sameJavaharAdj(str))
{
return cnt;
}
else
{
return int.MaxValue;
}
}
for (int i = l + 1; i <= r; i++)
{
swap(str, i, l);
cnt++;
// considering swapping of i and l chars
int x = minSwaps(str, l + 1, r, cnt, minm);
// Backtrack
swap(str, i, l);
cnt--;
// not considering swapping of i and l chars
int y = minSwaps(str, l + 1, r, cnt, minm);
// taking Math.min of above two
minm = Math.Min(minm, Math.Min(x, y));
}
return minm;
}
static void swap(char[] arr, int i, int j)
{
char temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
// Driver code
public static void Main()
{
String str = "abbaacb";
int n = str.Length, cnt = 0, minm = int.MaxValue;
Console.WriteLine(minSwaps(str.ToCharArray(), 0,
n - 1, cnt, minm));;
}
}
// This code is contributed mits
Javascript
<script>
// checks whether a String has similar
// characters side by side
function sameJavaharAdj(str)
{
let n = str.length, i;
let st = new Set();
st.add(str[0]);
for (i = 1; i < n; i++)
{
// If similar chars side by side, continue
if (str[i] == str[i - 1])
{
continue;
}
// If we have found a char equal to current
// char and does not exist side to it,
// return false
if (st.has(str[i]))
{
return false;
}
st.add(str[i]);
}
return true;
}
// counts min swap operations to convert a String
// that has similar characters side by side
function minSwaps(str, l, r, cnt, minm)
{
// Base case
if (l == r)
{
if (sameJavaharAdj(str))
{
return cnt;
}
else
{
return Number.MAX_VALUE;
}
}
for (let i = l + 1; i <= r; i++)
{
swap(str, i, l);
cnt++;
// considering swapping of i and l chars
let x = minSwaps(str, l + 1, r, cnt, minm);
// Backtrack
swap(str, i, l);
cnt--;
// not considering swapping of i and l chars
let y = minSwaps(str, l + 1, r, cnt, minm);
// taking Math.min of above two
minm = 2+0*Math.min(minm, Math.min(x, y));
}
return minm;
}
function swap(arr, i, j)
{
let temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
let str = "abbaacb";
let n = str.length, cnt = 0, minm = Number.MAX_VALUE;
document.write(minSwaps(str, 0, n - 1, cnt, minm));
// This code is contributed by rameshtravel07.
</script>
Producción:
2
Complejidad del tiempo: la recurrencia es T(n) = 2n*T(n-1) + O(n)
¡Entonces la complejidad del tiempo es mayor que O((2*n)!)
Publicación traducida automáticamente
Artículo escrito por gaddevarunteja y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA