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 problema se resolvió utilizando un enfoque codicioso en la publicación anterior . En esta publicación, discutiremos un enfoque de programación dinámica para resolver el mismo problema. Cree una función charVal que devuelva 0, 1 o 2 según el carácter.
Se hace una función recursiva que llama a la función charVal para obtener el i-ésimo valor, y si este es igual al anterior, entonces solo se usan los otros dos estados (1 o 2, 0 o 1, 0 o 2) en i-ésimo carácter. Si no es igual al anterior, no se realizan cambios. Se utiliza una array dp[][] para la memorización. El caso base es cuando todos los puestos están ocupados. Si se vuelve a visitar alguno de los estados, devuelva el valor que está almacenado en la array dp[][] . DP[i][j] significa que la i-ésima posición se llena con el j-ésimo carácter.
A continuación se muestra la implementación del problema anterior:
C++
// C++ program to count the minimal
// replacements such that adjacent characters
// are unequal
#include <bits/stdc++.h>
using namespace std;
// function to return integer value
// of i-th character in the string
int charVal(string s, int i)
{
if (s[i] == '0')
return 0;
else if (s[i] == '1')
return 1;
else
return 2;
}
// Function to count the number of
// minimal replacements
int countMinimalReplacements(string s, int i,
int prev, int dp[][3], int n)
{
// If the string has reached the end
if (i == n) {
return 0;
}
// If the state has been visited previously
if (dp[i][prev] != -1)
return dp[i][prev];
// Get the current value of character
int val = charVal(s, i);
int ans = INT_MAX;
// If it is equal then change it
if (val == prev) {
int val = 0;
// All possible changes
for (int cur = 0; cur <= 2; cur++) {
if (cur == prev)
continue;
// Change done
val = 1 + countMinimalReplacements(s, i + 1, cur, dp, n);
ans = min(ans, val);
}
}
else // If same no change
ans = countMinimalReplacements(s, i + 1, val, dp, n);
return dp[i][val] = ans;
}
// Driver Code
int main()
{
string s = "201220211";
// Length of string
int n = s.length();
// Create a DP array
int dp[n][3];
memset(dp, -1, sizeof dp);
// First character
int val = charVal(s, 0);
// Function to find minimal replacements
cout << countMinimalReplacements(s, 1, val, dp, n);
return 0;
}
Java
// Java program to count the minimal
// replacements such that adjacent characters
// are unequal
class GFG
{
// function to return integer value
// of i-th character in the string
static int charVal(String s, int i)
{
if (s.charAt(i) == '0')
{
return 0;
}
else if (s.charAt(i) == '1')
{
return 1;
}
else
{
return 2;
}
}
// Function to count the number of
// minimal replacements
static int countMinimalReplacements(String s, int i,
int prev, int dp[][], int n)
{
// If the string has reached the end
if (i == n)
{
return 0;
}
// If the state has been visited previously
if (dp[i][prev] != -1)
{
return dp[i][prev];
}
// Get the current value of character
int val = charVal(s, i);
int ans = Integer.MAX_VALUE;
// If it is equal then change it
if (val == prev)
{
val = 0;
// All possible changes
for (int cur = 0; cur <= 2; cur++)
{
if (cur == prev)
{
continue;
}
// Change done
val = 1 + countMinimalReplacements(s,
i + 1, cur, dp, n);
ans = Math.min(ans, val);
}
} else // If same no change
{
ans = countMinimalReplacements(s, i + 1,
val, dp, n);
}
return dp[i][val] = ans;
}
// Driver Code
public static void main(String[] args)
{
String s = "201220211";
// Length of string
int n = s.length();
// Create a DP array
int dp[][] = new int[n][3];
for (int i = 0; i < n; i++)
{
for (int j = 0; j < 3; j++)
{
dp[i][j] = -1;
}
}
// First character
int val = charVal(s, 0);
// Function to find minimal replacements
System.out.println(countMinimalReplacements(s, 1,
val, dp, n));
}
}
// This code is contributed by PrinciRaj1992
Python3
# Python 3 program to count the minimal # replacements such that adjacent characters # are unequal import sys # function to return integer value # of i-th character in the string def charVal(s, i): if (s[i] == '0'): return 0 elif (s[i] == '1'): return 1 else: return 2 # Function to count the number of # minimal replacements def countMinimalReplacements(s,i,prev, dp, n): # If the string has reached the end if (i == n): return 0 # If the state has been visited previously if (dp[i][prev] != -1): return dp[i][prev] # Get the current value of character val = charVal(s, i) ans = sys.maxsize # If it is equal then change it if (val == prev): val = 0 # All possible changes for cur in range(3): if (cur == prev): continue # Change done val = 1 + countMinimalReplacements(s, i + 1, cur, dp, n) ans = min(ans, val) # If same no change else: ans = countMinimalReplacements(s, i + 1, val, dp, n) dp[i][val] = ans return dp[i][val] # Driver Code if __name__ == '__main__': s = "201220211" # Length of string n = len(s) # Create a DP array dp = [[-1 for i in range(3)] for i in range(n)] # First character val = charVal(s, 0) # Function to find minimal replacements print(countMinimalReplacements(s, 1, val, dp, n)) # 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
{
// function to return integer value
// of i-th character in the string
static int charVal(string s, int i)
{
if (s[i] == '0')
{
return 0;
}
else if (s[i] == '1')
{
return 1;
}
else
{
return 2;
}
}
// Function to count the number of
// minimal replacements
static int countMinimalReplacements(string s, int i,
int prev, int [,]dp, int n)
{
// If the string has reached the end
if (i == n)
{
return 0;
}
// If the state has been visited previously
if (dp[i,prev] != -1)
{
return dp[i,prev];
}
// Get the current value of character
int val = charVal(s, i);
int ans = int.MaxValue;
// If it is equal then change it
if (val == prev)
{
val = 0;
// All possible changes
for (int cur = 0; cur <= 2; cur++)
{
if (cur == prev)
{
continue;
}
// Change done
val = 1 + countMinimalReplacements(s,
i + 1, cur, dp, n);
ans = Math.Min(ans, val);
}
}
else // If same no change
{
ans = countMinimalReplacements(s, i + 1,
val, dp, n);
}
return dp[i,val] = ans;
}
// Driver Code
public static void Main()
{
string s = "201220211";
// Length of string
int n = s.Length;
// Create a DP array
int [,]dp = new int[n,3];
for (int i = 0; i < n; i++)
{
for (int j = 0; j < 3; j++)
{
dp[i,j] = -1;
}
}
// First character
int val = charVal(s, 0);
// Function to find minimal replacements
Console.WriteLine(countMinimalReplacements(s, 1,
val, dp, n));
}
}
// This code is contributed by Ryuga
Javascript
<script>
// JavaScript program to count the minimal
// replacements such that adjacent characters
// are unequal
// function to return integer value
// of i-th character in the string
function charVal( s , i) {
if (s.charAt(i) == '0') {
return 0;
} else if (s.charAt(i) == '1') {
return 1;
} else {
return 2;
}
}
// Function to count the number of
// minimal replacements
function countMinimalReplacements( s , i , prev , dp , n)
{
// If the string has reached the end
if (i == n) {
return 0;
}
// If the state has been visited previously
if (dp[i][prev] != -1) {
return dp[i][prev];
}
// Get the current value of character
var val = charVal(s, i);
var ans = Number.MAX_VALUE;
// If it is equal then change it
if (val == prev) {
val = 0;
// All possible changes
for (var cur = 0; cur <= 2; cur++) {
if (cur == prev) {
continue;
}
// Change done
val = 1 +
countMinimalReplacements(s, i + 1, cur, dp, n);
ans = Math.min(ans, val);
}
} else // If same no change
{
ans =
countMinimalReplacements(s, i + 1, val, dp, n);
}
return dp[i][val] = ans;
}
// Driver Code
var s = "201220211";
// Length of string
var n = s.length;
// Create a DP array
var dp = Array(n).fill().map(()=>Array(3).fill(0));
for (var i = 0; i < n; i++) {
for (var j = 0; j < 3; j++) {
dp[i][j] = -1;
}
}
// First character
var val = charVal(s, 0);
// Function to find minimal replacements
document.write(countMinimalReplacements(s, 1, val, dp, n));
// This code contributed by Rajput-Ji
</script>
Producción:
2
Complejidad de tiempo: O (3 * N), ya que estamos usando recursividad con memorización nos costará O (N) tiempo ya que evitaremos llamadas recursivas innecesarias. Donde N es el número de caracteres de la string.
Espacio auxiliar: O(3*N), ya que estamos usando espacio adicional para la array DP. Donde N es el número de caracteres de la string.