Dada una string S de longitud N y un número entero K , la tarea es encontrar la longitud de la subsecuencia más larga de modo que la diferencia entre los valores ASCII de los caracteres adyacentes en la subsecuencia no sea mayor que K.
Ejemplos:
Input: N = 7, K = 2, S = "afcbedg" Output: 4 Explanation: Longest special sequence present in "afcbedg" is a, c, b, d. It is special because |a - c| <= 2, |c - b| <= 2 and | b-d| <= 2 Input: N = 13, K = 3, S = "geeksforgeeks" Output: 7
Enfoque ingenuo: una solución de fuerza bruta es generar todas las subsecuencias posibles de varias longitudes y calcular la longitud máxima de la subsecuencia válida. La complejidad del tiempo será exponencial.
Enfoque eficiente: un enfoque eficiente es utilizar el concepto Programación dinámica
- Cree una array dp de 0 con un tamaño igual a la longitud de la string.
- Cree una array de soporte max_length con 0 de tamaño 26.
- Itere la string carácter por carácter y para cada carácter determine los límites superior e inferior.
- Iterar bucle anidado en el rango de límites inferior y superior.
- Rellene la array dp con el valor máximo entre los índices dp actuales y los índices max_length actuales+1.
- Rellene la array max_length con el valor máximo entre los índices dp actuales y los índices max_length actuales.
- La longitud más larga de la subsecuencia es el valor máximo en la array dp .
- Consideremos un ejemplo:
la string de entrada s es «afcbedg» y k es 2
- para la primera iteración el valor de i es ‘a’ y el rango de j es (0, 2)
y dp actual = [1, 0, 0, 0, 0, 0, 0]- para la segunda iteración el valor de i es ‘f’ y el rango de j es (3, 7)
y dp actual = [1, 1, 0, 0, 0, 0, 0]- para la tercera iteración el valor de i es ‘c’ y el rango de j es (0, 4)
y dp actual = [1, 1, 2, 0, 0, 0, 0]- para la cuarta iteración, el valor de i es ‘b’ y el rango de j es (0, 3)
y el dp actual = [1, 1, 2, 3, 0, 0, 0]- para la quinta iteración el valor de i es ‘e’ y el rango de j es (2, 6)
y dp actual = [1, 1, 2, 3, 3, 0, 0]- para la sexta iteración el valor de i es ‘d’ y el rango de j es (1, 5)
y el dp actual = [1, 1, 2, 3, 3, 4, 0]- para la séptima iteración, el valor de i es ‘g’ y el rango de j es (4, 8)
y el dp actual = [1, 1, 2, 3, 3, 4, 4]la longitud más larga es el valor máximo en dp, por lo que la longitud máxima es 4
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
// Function to find
// the longest Special Sequence
int longest_subseq(int n, int k, string s)
{
// Creating a list with
// all 0's of size
// equal to the length of string
vector<int> dp(n, 0);
// Supporting list with
// all 0's of size 26 since
// the given string consists
// of only lower case alphabets
int max_length[26] = {0};
for (int i = 0; i < n; i++)
{
// Converting the ascii value to
// list indices
int curr = s[i] - 'a';
// Determining the lower bound
int lower = max(0, curr - k);
// Determining the upper bound
int upper = min(25, curr + k);
// Filling the dp array with values
for (int j = lower; j < upper + 1; j++)
{
dp[i] = max(dp[i], max_length[j] + 1);
}
//Filling the max_length array with max
//length of subsequence till now
max_length[curr] = max(dp[i], max_length[curr]);
}
int ans = 0;
for(int i:dp) ans = max(i, ans);
// return the max length of subsequence
return ans;
}
// Driver Code
int main()
{
string s = "geeksforgeeks";
int n = s.size();
int k = 3;
cout << (longest_subseq(n, k, s));
return 0;
}
// This code is contributed by Mohit Kumar
Java
// Java program for the above approach
class GFG
{
// Function to find
// the longest Special Sequence
static int longest_subseq(int n, int k, String s)
{
// Creating a list with
// all 0's of size
// equal to the length of String
int []dp = new int[n];
// Supporting list with
// all 0's of size 26 since
// the given String consists
// of only lower case alphabets
int []max_length = new int[26];
for (int i = 0; i < n; i++)
{
// Converting the ascii value to
// list indices
int curr = s.charAt(i) - 'a';
// Determining the lower bound
int lower = Math.max(0, curr - k);
// Determining the upper bound
int upper = Math.min(25, curr + k);
// Filling the dp array with values
for (int j = lower; j < upper + 1; j++)
{
dp[i] = Math.max(dp[i], max_length[j] + 1);
}
// Filling the max_length array with max
// length of subsequence till now
max_length[curr] = Math.max(dp[i], max_length[curr]);
}
int ans = 0;
for(int i:dp) ans = Math.max(i, ans);
// return the max length of subsequence
return ans;
}
// Driver Code
public static void main(String[] args)
{
String s = "geeksforgeeks";
int n = s.length();
int k = 3;
System.out.print(longest_subseq(n, k, s));
}
}
// This code is contributed by 29AjayKumar
Python3
# Function to find
# the longest Special Sequence
def longest_subseq(n, k, s):
# Creating a list with
# all 0's of size
# equal to the length of string
dp = [0] * n
# Supporting list with
# all 0's of size 26 since
# the given string consists
# of only lower case alphabets
max_length = [0] * 26
for i in range(n):
# Converting the ascii value to
# list indices
curr = ord(s[i]) - ord('a')
# Determining the lower bound
lower = max(0, curr - k)
# Determining the upper bound
upper = min(25, curr + k)
# Filling the dp array with values
for j in range(lower, upper + 1):
dp[i] = max(dp[i], max_length[j]+1)
# Filling the max_length array with max
# length of subsequence till now
max_length[curr] = max(dp[i], max_length[curr])
# return the max length of subsequence
return max(dp)
# driver code
def main():
s = "geeksforgeeks"
n = len(s)
k = 3
print(longest_subseq(n, k, s))
main()
C#
// C# program for the above approach
using System;
class GFG
{
// Function to find
// the longest Special Sequence
static int longest_subseq(int n, int k, String s)
{
// Creating a list with
// all 0's of size
// equal to the length of String
int []dp = new int[n];
// Supporting list with
// all 0's of size 26 since
// the given String consists
// of only lower case alphabets
int []max_length = new int[26];
for (int i = 0; i < n; i++)
{
// Converting the ascii value to
// list indices
int curr = s[i] - 'a';
// Determining the lower bound
int lower = Math.Max(0, curr - k);
// Determining the upper bound
int upper = Math.Min(25, curr + k);
// Filling the dp array with values
for (int j = lower; j < upper + 1; j++)
{
dp[i] = Math.Max(dp[i], max_length[j] + 1);
}
// Filling the max_length array with max
// length of subsequence till now
max_length[curr] = Math.Max(dp[i], max_length[curr]);
}
int ans = 0;
foreach(int i in dp) ans = Math.Max(i, ans);
// return the max length of subsequence
return ans;
}
// Driver Code
public static void Main(String[] args)
{
String s = "geeksforgeeks";
int n = s.Length;
int k = 3;
Console.Write(longest_subseq(n, k, s));
}
}
// This code is contributed by Rajput-Ji
Javascript
<script>
// Javascript program for the above approach
// Function to find
// the longest Special Sequence
function longest_subseq(n, k, s)
{
// Creating a list with
// all 0's of size
// equal to the length of String
let dp = new Array(n);
// Supporting list with
// all 0's of size 26 since
// the given String consists
// of only lower case alphabets
let max_length = new Array(26);
for(let i = 0; i < 26; i++)
{
max_length[i] = 0;
dp[i] = 0;
}
for (let i = 0; i < n; i++)
{
// Converting the ascii value to
// list indices
let curr = s[i].charCodeAt(0) - 'a'.charCodeAt(0);
// Determining the lower bound
let lower = Math.max(0, curr - k);
// Determining the upper bound
let upper = Math.min(25, curr + k);
// Filling the dp array with values
for (let j = lower; j < upper + 1; j++)
{
dp[i] = Math.max(dp[i], max_length[j] + 1);
}
// Filling the max_length array with max
// length of subsequence till now
max_length[curr] = Math.max(dp[i], max_length[curr]);
}
let ans = 0;
ans = Math.max(...dp)
// return the max length of subsequence
return ans;
}
// Driver Code
let s = "geeksforgeeks";
let n = s.length;
let k = 3;
document.write(longest_subseq(n, k, s));
// This code is contributed by unknown2108
</script>
Producción:
7
Complejidad temporal: O(N)
Espacio auxiliar: O(N)
Publicación traducida automáticamente
Artículo escrito por imran_shaik y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA