Dada una string de ‘0’, ‘1’ y ‘2’. La tarea es encontrar el número mínimo de reemplazos para que los caracteres adyacentes no sean iguales.
Ejemplos:
Entrada: s = “201220211”
Salida: 2 La
string resultante después de los cambios es 201210210
Entrada: s = “0120102”
Salida: 0
Enfoque: El siguiente problema se puede resolver usando el método codicioso. Podemos comparar con avidez cada par adyacente. Si los pares adyacentes que son caracteres en i – th e i- 1th son iguales, entonces reemplace el i -th carácter con un carácter que no sea igual al carácter en i- 1th e i+ 1th index. En el caso del último par adyacente, simplemente reemplácelo con el carácter que no es igual al carácter en el índice i- 1th .
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program to count the minimal
// replacements such that adjacent characters
// are unequal
#include <bits/stdc++.h>
using namespace std;
// Function to count the number of
// minimal replacements
int countMinimalReplacements(string s)
{
// Find the length of the string
int n = s.length();
int cnt = 0;
// Iterate in the string
for (int i = 1; i < n; i++) {
// Check if adjacent is similar
if (s[i] == s[i - 1]) {
cnt += 1;
// If not the last pair
if (i != (n - 1)) {
// Check for character which is
// not same in i+1 and i-1
for (auto it : "012") {
if (it != s[i + 1] &&
it != s[i - 1]) {
s[i] = it;
break;
}
}
}
else // Last pair
{
// Check for character which is
// not same in i-1 index
for (auto it : "012") {
if (it != s[i - 1]) {
s[i] = it;
break;
}
}
}
}
}
return cnt;
}
// Driver Code
int main()
{
string s = "201220211";
cout << countMinimalReplacements(s);
return 0;
}
Java
// Java program to count the minimal
// replacements such that adjacent
// characters are unequal
class GFG
{
static final int MAX = 26;
// Function to count the number of
// minimal replacements
static int countMinimalReplacements(char[] s)
{
// Find the length of the String
int n = s.length;
int cnt = 0;
// Iterate in the String
for (int i = 1; i < n; i++)
{
// Check if adjacent is similar
if (s[i] == s[i - 1])
{
cnt += 1;
// If not the last pair
if (i != (n - 1))
{
// Check for character which is
// not same in i+1 and i-1
for (char it : "012".toCharArray())
{
if (it != s[i + 1]
&& it != s[i - 1])
{
s[i] = it;
break;
}
}
}
else // Last pair
{
// Check for character which is
// not same in i-1 index
for (char it : "012".toCharArray())
{
if (it != s[i - 1])
{
s[i] = it;
break;
}
}
}
}
}
return cnt;
}
// Driver Code
public static void main(String[] args)
{
String s = "201220211";
System.out.println(countMinimalReplacements(s.toCharArray()));
}
}
// This code is contributed by 29AjayKumar
Python3
# Python 3 program to count the minimal # replacements such that adjacent # characters are unequal # Function to count the number of # minimal replacements def countMinimalReplacements(s): # Find the length of the string n = len(s) cnt = 0 # Iterate in the string for i in range(1, n): # Check if adjacent is similar if (s[i] == s[i - 1]): cnt += 1; # If not the last pair if (i != (n - 1)): # Check for character which is # not same in i+1 and i-1 s = list(s) for j in "012": if (j != s[i + 1] and j != s[i - 1]): s[i] = j break s = ''.join(s) # Last pair else: # Check for character which is # not same in i-1 index s = list(s) for k in "012": if (k != s[i - 1]): s[i] = k break s = ''.join(s) return cnt # Driver Code if __name__ == '__main__': s = "201220211" print(countMinimalReplacements(s)) # This code is contributed by # Surendra_Gangwar
C#
// C# program to count the minimal
// replacements such that adjacent
// characters are unequal
using System;
class GFG
{
static readonly int MAX = 26;
// Function to count the number of
// minimal replacements
static int countMinimalReplacements(char[] s)
{
// Find the length of the String
int n = s.Length;
int cnt = 0;
// Iterate in the String
for (int i = 1; i < n; i++)
{
// Check if adjacent is similar
if (s[i] == s[i - 1])
{
cnt += 1;
// If not the last pair
if (i != (n - 1))
{
// Check for character which is
// not same in i+1 and i-1
foreach (char it in "012".ToCharArray())
{
if (it != s[i + 1] &&
it != s[i - 1])
{
s[i] = it;
break;
}
}
}
else // Last pair
{
// Check for character which is
// not same in i-1 index
foreach (char it in "012".ToCharArray())
{
if (it != s[i - 1])
{
s[i] = it;
break;
}
}
}
}
}
return cnt;
}
// Driver Code
public static void Main(String[] args)
{
String s = "201220211";
Console.WriteLine(countMinimalReplacements(s.ToCharArray()));
}
}
// This code is contributed by Rajput-Ji
PHP
<?php
// PHP program to count the minimal
// replacements such that adjacent
// characters are unequal
// Function to count the number of
// minimal replacements
function countMinimalReplacements($s)
{
// Find the length of the string
$n = strlen($s);
$cnt = 0;
$str = "012";
// Iterate in the string
for ($i = 1; $i < $n; $i++)
{
// Check if adjacent is similar
if ($s[$i] == $s[$i - 1])
{
$cnt += 1;
// If not the last pair
if ($i != ($n - 1))
{
// Check for character which is
// not same in i+1 and i-1
for ($it = 0 ; $it < strlen($str); $it++)
{
if ($str[$it] != $s[$i + 1] &&
$str[$it] != $s[$i - 1])
{
$s[$i] = $str[$it];
break;
}
}
}
else // Last pair
{
// Check for character which is
// not same in i-1 index
for ($it = 0 ; $it< strlen($str); $it++)
{
if ($str[$it] != $s[$i - 1])
{
$s[$i] = $str[$it];
break;
}
}
}
}
}
return $cnt;
}
// Driver Code
$s = "201220211";
echo countMinimalReplacements($s);
// This code is contributed by Ryuga
?>
Javascript
<script>
// JavaScript program to count the minimal
// replacements such that adjacent
// characters are unequal
// Function to count the number of
// minimal replacements
function countMinimalReplacements(s) {
// Find the length of the string
var n = s.length;
var cnt = 0;
var str = "012";
// Iterate in the string
for (var i = 1; i < n; i++) {
// Check if adjacent is similar
if (s[i] === s[i - 1]) {
cnt += 1;
// If not the last pair
if (i !== n - 1) {
// Check for character which is
// not same in i+1 and i-1
for (var it = 0; it < str.length; it++) {
if (str[it] !== s[i + 1] && str[it] !== s[i - 1]) {
s[i] = str[it];
break;
}
}
} // Last pair
else {
// Check for character which is
// not same in i-1 index
for (var it = 0; it < str.length; it++) {
if (str[it] !== s[i - 1]) {
s[i] = str[it];
break;
}
}
}
}
}
return cnt;
}
// Driver Code
var s = "201220211";
document.write(countMinimalReplacements(s));
</script>
Producción:
2
Complejidad de tiempo: O (3 * n), ya que estamos usando un ciclo para atravesar n veces. Donde n es el número de elementos de la array.
Espacio auxiliar: O(1), ya que no estamos utilizando ningún espacio adicional.