Dada una string S de longitud N , que consta solo de alfabetos ingleses en minúsculas, la tarea es encontrar la longitud mínima posible de codificación de longitud de ejecución que se puede generar eliminando como máximo K caracteres de la string S .
Ejemplos:
Entrada: S = “abbbcdcdd”, N = 9, K = 2
Salida: 5
Explicación: Una forma posible es eliminar ambas ocurrencias de ‘c’ de S.
La nueva string generada es “abbbddd” cuya codificación de longitud de ejecución es “ab3d3”.
Por lo tanto, la longitud de la string codificada es 5.Entrada: S = “aabbca”, N = 6, K = 3
Salida: 2
Explicación: Una forma posible es eliminar tanto las apariciones de ‘b’ como una de ‘c’.
La nueva string generada es «aaa» cuya codificación de longitud de ejecución es «a3».
Por lo tanto, la longitud de la string codificada es 2
Enfoque ingenuo: el enfoque más simple para resolver el problema es eliminar cada combinación de K caracteres de la string y calcular su codificación de longitud de ejecución respectiva . Finalmente, imprima la longitud de la codificación de longitud de ejecución más pequeña obtenida.
Complejidad de Tiempo: O(K * N!(N – K)! * K!)
Espacio Auxiliar: O(K)
Enfoque eficiente: para optimizar el enfoque anterior, siga los pasos a continuación para resolver el problema:
- Mantenga una array auxiliar dp[n][k][26][n] , donde dp[idx][K][last][count] denota la codificación de longitud de ejecución mínima obtenida a partir del índice idx donde, K denota el número de eliminaciones restantes, último denota el último carácter con recuento de frecuencia hasta el momento.
- Para cada carácter, existen dos posibilidades, ya sea para eliminar el carácter o para retenerlo.
- Considere que el carácter actual en el índice idx se elimina y calcule recursivamente la codificación mínima de longitud de ejecución obtenida al pasar los parámetros (idx + 1, K – 1, último, conteo)
- Ahora, considere que el carácter actual en el índice idx se conserva y calcule recursivamente la codificación mínima de longitud de ejecución para los siguientes dos casos:
- Si S[idx] = último: calcule la codificación de longitud de ejecución mínima pasando los parámetros (idx + 1, K, S[idx], count + 1) .
- De lo contrario, calcule la codificación de longitud de ejecución mínima pasando los parámetros (idx + 1, K, S[idx], 1) .
- Devuelva el mínimo de los valores calculados anteriormente y repita los pasos anteriores para todos los índices de la string.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ Program to implement
// the above approach
#include <bits/stdc++.h>
using namespace std;
#define maxN 20
int dp[maxN][maxN][27][maxN];
// Function which solves the desired problem
int solve(string& s, int n, int idx,
int k, char last = 123,
int count = 0)
{
// idx: current index in s
// k: Remaining number of deletions
// last: Previous character
// count: Number of occurrences
// of the previous character
// Base Case
if (k < 0)
return n + 1;
// If the entire string has
// been traversed
if (idx == n)
return 0;
int& ans = dp[idx][k][last - 'a'][count];
// If precomputed subproblem
// occurred
if (ans != -1)
return ans;
ans = n + 1;
// Minimum run length encoding by
// removing the current character
ans = min(ans,
solve(s, n, idx + 1, k - 1, last, count));
// Minimum run length encoding by
// retaining the current character
int inc = 0;
if (count == 1 || count == 9
|| count == 99)
inc = 1;
// If the current and the
// previous characters match
if (last == s[idx]) {
ans = min(ans,
inc + solve(s, n, idx + 1, k, s[idx],
count + 1));
}
// Otherwise
else {
ans = min(ans,
1 + solve(s, n, idx + 1, k, s[idx], 1));
}
return ans;
}
// Function to return minimum run-length encoding
// for string s by removing atmost k characters
int MinRunLengthEncoding(string& s, int n, int k)
{
memset(dp, -1, sizeof(dp));
return solve(s, n, 0, k);
}
// Driver Code
int main()
{
string S = "abbbcdcdd";
int N = 9, K = 2;
cout << MinRunLengthEncoding(S, N, K);
return 0;
}
Java
// Java program to implement
// the above approach
import java.util.*;
class GFG{
static int maxN = 20;
static int dp[][][][] = new int[maxN][maxN][27][maxN];
// Function which solves the desired problem
public static int solve(String s, int n,
int idx, int k,
char last, int count)
{
// idx: current index in s
// k: Remaining number of deletions
// last: Previous character
// count: Number of occurrences
// of the previous character
// Base Case
if (k < 0)
return n + 1;
// If the entire string has
// been traversed
if (idx == n)
return 0;
int ans = dp[idx][k][last - 'a'][count];
// If precomputed subproblem
// occurred
if (ans != -1)
return ans;
ans = n + 1;
// Minimum run length encoding by
// removing the current character
ans = Math.min(ans, solve(s, n, idx + 1,
k - 1, last,
count));
// Minimum run length encoding by
// retaining the current character
int inc = 0;
if (count == 1 || count == 9 || count == 99)
inc = 1;
// If the current and the
// previous characters match
if (last == s.charAt(idx))
{
ans = Math.min(ans, inc + solve(s, n, idx + 1,
k, s.charAt(idx),
count + 1));
}
// Otherwise
else
{
ans = Math.min(ans, 1 + solve(s, n, idx + 1, k,
s.charAt(idx), 1));
}
return dp[idx][k][last - 'a'][count] = ans;
}
// Function to return minimum run-length encoding
// for string s by removing atmost k characters
public static int MinRunLengthEncoding(String s, int n,
int k)
{
for(int i[][][] : dp)
for(int j[][] : i)
for(int p[] : j)
Arrays.fill(p, -1);
return solve(s, n, 0, k, (char)123, 0);
}
// Driver Code
public static void main(String args[])
{
String S = "abbbcdcdd";
int N = 9, K = 2;
System.out.println(MinRunLengthEncoding(S, N, K));
}
}
// This code is contributed by hemanth gadarla
Python3
# Python3 program to implement
# the above approach
maxN = 20
dp = [[[[0 for i in range(maxN)]
for j in range(27)]
for k in range(27)]
for l in range(maxN)]
# Function which solves the desired problem
def solve(s, n, idx, k, last, count):
# idx: current index in s
# k: Remaining number of deletions
# last: Previous character
# count: Number of occurrences
# of the previous character
# Base Case
if (k < 0):
return n + 1
# If the entire string has
# been traversed
if (idx == n):
return 0
ans = dp[idx][k][ord(last) - ord('a')][count]
# If precomputed subproblem
# occurred
if (ans != -1):
return ans
ans = n + 1
# Minimum run length encoding by
# removing the current character
ans = min(ans, solve(s, n, idx + 1,
k - 1, last, count))
# Minimum run length encoding by
# retaining the current character
inc = 0
if (count == 1 or count == 9 or
count == 99):
inc = 1
# If the current and the
# previous characters match
if (last == s[idx]):
ans = min(ans, inc + solve(s, n, idx + 1, k,
s[idx], count + 1))
# Otherwise
else:
ans = max(ans, 1 + solve(s, n, idx + 1,
k, s[idx], 1))
dp[idx][k][ord(last) - ord('a')][count] = ans
#print(ans)
return dp[idx][k][ord(last) - ord('a')][count]
# Function to return minimum run-length encoding
# for string s by removing atmost k characters
def MinRunLengthEncoding(s, n, k):
for i in range(maxN):
for j in range(27):
for k in range(27):
for l in range(maxN):
dp[i][j][k][l] = -1
return solve(s, n, 0, k, chr(123), 0) - 1
# Driver Code
if __name__ == '__main__':
S = "abbbcdcdd"
N = 9
K = 2
print(MinRunLengthEncoding(S, N, K))
# This code is contributed by gauravrajput1
C#
// C# program to implement
// the above approach
using System;
class GFG{
static int maxN = 20;
static int [,,,]dp =
new int[maxN, maxN,
27, maxN];
// Function which solves
// the desired problem
public static int solve(String s, int n,
int idx, int k,
char last, int count)
{
// idx: current index in s
// k: Remaining number of deletions
// last: Previous character
// count: Number of occurrences
// of the previous character
// Base Case
if (k < 0)
return n + 1;
// If the entire string
// has been traversed
if (idx == n)
return 0;
int ans = dp[idx, k, last -
'a', count];
// If precomputed subproblem
// occurred
if (ans != -1)
return ans;
ans = n + 1;
// Minimum run length encoding by
// removing the current character
ans = Math.Min(ans,
solve(s, n, idx + 1,
k - 1, last,
count));
// Minimum run length encoding by
// retaining the current character
int inc = 0;
if (count == 1 || count == 9 ||
count == 99)
inc = 1;
// If the current and the
// previous characters match
if (last == s[idx])
{
ans = Math.Min(ans, inc +
solve(s, n, idx + 1,
k, s[idx],
count + 1));
}
// Otherwise
else
{
ans = Math.Min(ans, 1 +
solve(s, n, idx + 1,
k, s[idx], 1));
}
return dp[idx, k, last -
'a', count] = ans;
}
// Function to return minimum
// run-length encoding for string
// s by removing atmost k characters
public static int MinRunLengthEncoding(String s,
int n, int k)
{
for (int i = 0; i < maxN; i++)
for (int j = 0; j < maxN; j++)
for (int p = 0; p < 27; p++)
for (int l = 0; l < maxN; l++)
dp[i, j, p, l] = -1;
return solve(s, n, 0,
k, (char)123, 0);
}
// Driver Code
public static void Main(String []args)
{
String S = "abbbcdcdd";
int N = 9, K = 2;
Console.WriteLine(
MinRunLengthEncoding(S,
N, K));
}
}
// This code is contributed by 29AjayKumar
Javascript
<script>
// JavaScript program to implement the above approach
let maxN = 20;
let dp = new Array(maxN);
// Function which solves the desired problem
function solve(s, n, idx, k, last, count)
{
// idx: current index in s
// k: Remaining number of deletions
// last: Previous character
// count: Number of occurrences
// of the previous character
// Base Case
if (k < 0)
return n + 1;
// If the entire string has
// been traversed
if (idx == n)
return 0;
let ans = dp[idx][k][last - 'a'.charCodeAt()][count];
// If precomputed subproblem
// occurred
if (ans != -1)
return ans;
ans = n + 1;
// Minimum run length encoding by
// removing the current character
ans = Math.min(ans, solve(s, n, idx + 1,
k - 1, last,
count));
// Minimum run length encoding by
// retaining the current character
let inc = 0;
if (count == 1 || count == 9 || count == 99)
inc = 1;
// If the current and the
// previous characters match
if (last == s[idx].charCodeAt())
{
ans = Math.min(ans, inc + solve(s, n, idx + 1,
k, s[idx].charCodeAt(),
count + 1));
}
// Otherwise
else
{
ans = Math.min(ans, 1 + solve(s, n, idx + 1, k,
s[idx].charCodeAt(), 1));
}
dp[idx][k][last - 'a'.charCodeAt()][count] = ans;
return dp[idx][k][last - 'a'.charCodeAt()][count];
}
// Function to return minimum run-length encoding
// for string s by removing atmost k characters
function MinRunLengthEncoding(s, n, k)
{
for(let i = 0; i < maxN; i++)
{
dp[i] = new Array(maxN);
for(let j = 0; j < maxN; j++)
{
dp[i][j] = new Array(27);
for(let k = 0; k < 27; k++)
{
dp[i][j][k] = new Array(maxN);
for(let l = 0; l < maxN; l++)
{
dp[i][j][k][l] = -1;
}
}
}
}
return solve(s, n, 0, k, 123, 0);
}
let S = "abbbcdcdd";
let N = 9, K = 2;
document.write(MinRunLengthEncoding(S, N, K));
</script>
Producción:
5
Tiempo Complejidad: O(26 * N 2 * K)
Espacio Auxiliar: O(26 * N 2 * K)
Publicación traducida automáticamente
Artículo escrito por shobhitgupta907 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA