Dada una string S , la tarea es encontrar la longitud de la subsecuencia creciente más larga presente en la string dada.
Una secuencia de caracteres colocados en orden creciente de sus valores ASCII se denomina secuencia creciente.
Ejemplos:
Entrada: S = “abcfgffs”
Salida: 6
Explicación: La subsecuencia “ abcfgs ” es la subsecuencia creciente más larga presente en la string. Por lo tanto, la longitud de la subsecuencia creciente más larga es 6 .Entrada: S = “aaabac”
Salida: 3
Enfoque: La idea es utilizar Programación Dinámica . Siga los pasos que se indican a continuación para resolver el problema:
- Inicialice una array, digamos dp[] de tamaño 26 , para almacenar en cada i- ésimo índice, la longitud de la subsecuencia creciente más larga que tenga (‘a’ + i) el carácter como el último carácter de la subsecuencia.
- Inicialice la variable, digamos lis , para almacenar la longitud de la subsecuencia requerida.
- Iterar sobre cada carácter de la string S .
- Para cada carácter encontrado, es decir, S[i] – ‘a’ , verifique todos los caracteres, digamos j , con valores ASCII menores que los del carácter actual.
- Inicialice una variable, digamos curr , para almacenar la longitud de LIS que termina con el carácter actual.
- Actualice curr con max(curr, dp[j]).
- Actualice la longitud del LIS, digamos lis, con max(lis, curr + 1).
- Actualice dp[S[i] – ‘a’] con un máximo de d[S[i] – ‘a’] y curr.
- Finalmente, imprima el valor de lis como la longitud requerida de LIS.
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 length of longest
// increasing subsequence in a string
int lisOtimised(string s)
{
// Stores at every i-th index, the
// length of the longest increasing
// subsequence ending with character i
int dp[30] = { 0 };
// Size of string
int N = s.size();
// Stores the length of LIS
int lis = INT_MIN;
// Iterate over each
// character of the string
for (int i = 0; i < N; i++) {
// Store position of the
// current character
int val = s[i] - 'a';
// Stores the length of LIS
// ending with current character
int curr = 0;
// Check for all characters
// less then current character
for (int j = 0; j < val; j++) {
curr = max(curr, dp[j]);
}
// Include current character
curr++;
// Update length of longest
// increasing subsequence
lis = max(lis, curr);
// Updating LIS for current character
dp[val] = max(dp[val], curr);
}
// Return the length of LIS
return lis;
}
// Driver Code
int main()
{
string s = "fdryutiaghfse";
cout << lisOtimised(s);
return 0;
}
Java
// Java program for the above approach
import java.util.*;
class GFG{
static int mn = -2147483648;
// Function to find length of longest
// increasing subsequence in a string
static int lisOtimised(String s)
{
// Stores at every i-th index, the
// length of the longest increasing
// subsequence ending with character i
int []dp = new int[30];
Arrays.fill(dp, 0);
// Size of string
int N = s.length();
// Stores the length of LIS
int lis = mn;
// Iterate over each
// character of the string
for(int i = 0; i < N; i++)
{
// Store position of the
// current character
int val = (int)s.charAt(i) - 97;
// Stores the length of LIS
// ending with current character
int curr = 0;
// Check for all characters
// less then current character
for(int j = 0; j < val; j++)
{
curr = Math.max(curr, dp[j]);
}
// Include current character
curr++;
// Update length of longest
// increasing subsequence
lis = Math.max(lis, curr);
// Updating LIS for current character
dp[val] = Math.max(dp[val], curr);
}
// Return the length of LIS
return lis;
}
// Driver Code
public static void main(String[] args)
{
String s = "fdryutiaghfse";
System.out.print(lisOtimised(s));
}
}
// This code is contributed by sanjoy_62
Python3
# Python3 program for the above approach
# Function to find length of longest
# increasing subsequence in a string
def lisOtimised(s):
# Stores at every i-th index, the
# length of the longest increasing
# subsequence ending with character i
dp = [0]*30
# Size of string
N = len(s)
# Stores the length of LIS
lis = -10**9
# Iterate over each
# character of the string
for i in range(N):
# Store position of the
# current character
val = ord(s[i]) - ord('a')
# Stores the length of LIS
# ending with current character
curr = 0
# Check for all characters
# less then current character
for j in range(val):
curr = max(curr, dp[j])
# Include current character
curr += 1
# Update length of longest
# increasing subsequence
lis = max(lis, curr)
# Updating LIS for current character
dp[val] = max(dp[val], curr)
# Return the length of LIS
return lis
# Driver Code
if __name__ == '__main__':
s = "fdryutiaghfse"
print (lisOtimised(s))
# This code is contributed by mohit kumar 29.
C#
// C# program for the above approach
using System;
using System.Collections.Generic;
class GFG
{
static int mn = -2147483648;
// Function to find length of longest
// increasing subsequence in a string
static int lisOtimised(string s)
{
// Stores at every i-th index, the
// length of the longest increasing
// subsequence ending with character i
int []dp = new int[30];
Array.Clear(dp, 0, 30);
// Size of string
int N = s.Length;
// Stores the length of LIS
int lis = mn;
// Iterate over each
// character of the string
for (int i = 0; i < N; i++) {
// Store position of the
// current character
int val = (int)s[i] - 97;
// Stores the length of LIS
// ending with current character
int curr = 0;
// Check for all characters
// less then current character
for (int j = 0; j < val; j++) {
curr = Math.Max(curr, dp[j]);
}
// Include current character
curr++;
// Update length of longest
// increasing subsequence
lis = Math.Max(lis, curr);
// Updating LIS for current character
dp[val] = Math.Max(dp[val], curr);
}
// Return the length of LIS
return lis;
}
// Driver Code
public static void Main()
{
string s = "fdryutiaghfse";
Console.Write(lisOtimised(s));
}
}
// This code is contributed by SURENDRA_GAANGWAR.
Javascript
<script>
// JavaScript program for the above approach
// Function to find length of longest
// increasing subsequence in a string
function lisOtimised( s)
{
// Stores at every i-th index, the
// length of the longest increasing
// subsequence ending with character i
let dp = new Array(30).fill(0);
// Size of string
let N = s.length;
// Stores the length of LIS
let lis = Number.MIN_VALUE;
// Iterate over each
// character of the string
for (let i = 0; i < N; i++) {
// Store position of the
// current character
let val = s.charCodeAt(i) - 'a'.charCodeAt(0);
// Stores the length of LIS
// ending with current character
let curr = 0;
// Check for all characters
// less then current character
for (let j = 0; j < val; j++) {
curr = Math.max(curr, dp[j]);
}
// Include current character
curr++;
// Update length of longest
// increasing subsequence
lis = Math.max(lis, curr);
// Updating LIS for current character
dp[val] = Math.max(dp[val], curr);
}
// Return the length of LIS
return lis;
}
// Driver Code
let s = "fdryutiaghfse";
document.write(lisOtimised(s));
</script>
Producción:
4
Complejidad temporal: O(N)
Espacio auxiliar: O(1)
Publicación traducida automáticamente
Artículo escrito por shubhampokhriyal2018 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA