Dada una string de ‘0’, ‘1’ y ‘2’. La tarea es encontrar los reemplazos mínimos en la string de modo que las diferencias entre los índices de los mismos caracteres sea divisible por 3.
Ejemplos:
Entrada: s = “2101200”
Salida: 3
1201201 o 2102102 puede ser la string resultante
que tiene 3 reemplazos.
Entrada: s = “012”
Salida: 0
Enfoque: puede haber 6 strings diferentes, de modo que la diferencia entre el índice de caracteres similares sea divisible por 3. Por lo tanto, genere las 6 strings diferentes y compare los reemplazos realizados con la string original. Almacene la string que tiene un número mínimo de reemplazos. Las diferentes strings se pueden generar usando next_permutation en C++.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program to find minimum replacements
// such that the difference between the
// index of the same characters
// is divisible by 3
#include <bits/stdc++.h>
using namespace std;
// Function to count the number of
// minimal replacements
int countMinimalReplacements(string s)
{
int n = s.length();
int mini = INT_MAX;
string dup = "012";
// Generate all permutations
do {
// Count the replacements
int dif = 0;
for (int i = 0; i < n; i++)
if (s[i] != dup[i % 3])
dif++;
mini = min(mini, dif);
} while (next_permutation(dup.begin(), dup.end()));
// Return the replacements
return mini;
}
// Driver Code
int main()
{
string s = "2101200";
cout << countMinimalReplacements(s);
return 0;
}
Java
// Java program to find minimum replacements
// such that the difference between the
// index of the same characters
// is divisible by 3
class GFG {
// Function to count the number of
// minimal replacements
static int countMinimalReplacements(String s)
{
int n = s.length();
int mini = Integer.MAX_VALUE;
char[] dup = "012".toCharArray();
// Generate all permutations
do {
// Count the replacements
int dif = 0;
for (int i = 0; i < n; i++) {
if (s.charAt(i) != dup[i % 3]) {
dif++;
}
}
mini = Math.min(mini, dif);
} while (next_permutation(dup));
// Return the replacements
return mini;
}
static boolean next_permutation(char[] p)
{
for (int a = p.length - 2; a >= 0; --a) {
if (p[a] < p[a + 1]) {
for (int b = p.length - 1;; --b) {
if (p[b] > p[a]) {
char t = p[a];
p[a] = p[b];
p[b] = t;
for (++a, b = p.length - 1; a < b; ++a, --b) {
t = p[a];
p[a] = p[b];
p[b] = t;
}
return true;
}
}
}
}
return false;
}
// Driver Code
public static void main(String args[])
{
String s = "2101200";
System.out.println(countMinimalReplacements(s));
}
}
/* This code contributed by PrinciRaj1992 */
C#
// C# program to find minimum replacements
// such that the difference between the
// index of the same characters
// is divisible by 3
using System;
class GFG {
// Function to count the number of
// minimal replacements
static int countMinimalReplacements(String s)
{
int n = s.Length;
int mini = int.MaxValue;
char[] dup = "012".ToCharArray();
// Generate all permutations
do {
// Count the replacements
int dif = 0;
for (int i = 0; i < n; i++) {
if (s[i] != dup[i % 3]) {
dif++;
}
}
mini = Math.Min(mini, dif);
} while (next_permutation(dup));
// Return the replacements
return mini;
}
static bool next_permutation(char[] p)
{
for (int a = p.Length - 2; a >= 0; --a) {
if (p[a] < p[a + 1]) {
for (int b = p.Length - 1;; --b) {
if (p[b] > p[a]) {
char t = p[a];
p[a] = p[b];
p[b] = t;
for (++a, b = p.Length - 1; a < b; ++a, --b) {
t = p[a];
p[a] = p[b];
p[b] = t;
}
return true;
}
}
}
}
return false;
}
// Driver Code
public static void Main(String[] args)
{
String s = "2101200";
Console.WriteLine(countMinimalReplacements(s));
}
}
// This code has been contributed by 29AjayKumar
Javascript
<script>
// JavaScript program to find minimum replacements
// such that the difference between the
// index of the same characters
// is divisible by 3
// Function to count the number of
// minimal replacements
function countMinimalReplacements(s) {
var n = s.length;
//Max Integer Value
var mini = 2147483647;
var dup = "012".split("");
// Generate all permutations
do {
// Count the replacements
var dif = 0;
for (var i = 0; i < n; i++) {
if (s[i] !== dup[i % 3]) {
dif++;
}
}
mini = Math.min(mini, dif);
} while (next_permutation(dup));
// Return the replacements
return mini;
}
function next_permutation(p) {
for (var a = p.length - 2; a >= 0; --a) {
if (p[a] < p[a + 1]) {
for (var b = p.length - 1; ; --b) {
if (p[b] > p[a]) {
var t = p[a];
p[a] = p[b];
p[b] = t;
for (++a, b = p.length - 1; a < b; ++a, --b) {
t = p[a];
p[a] = p[b];
p[b] = t;
}
return true;
}
}
}
}
return false;
}
// Driver Code
var s = "2101200";
document.write(countMinimalReplacements(s));
</script>
Producción:
3
Complejidad temporal: O(3*N), ya que somos un bucle para recorrer N veces. Donde n es la longitud de la string.
Espacio auxiliar: O(1), ya que no estamos utilizando ningún espacio adicional.