Dada la string S , la tarea es encontrar la longitud de la subsecuencia más larga de los alfabetos en minúsculas consecutivos.
Ejemplos:
Entrada: S = “acbdcfhg”
Salida: 3
Explicación:
La string “abc” es la subsecuencia más larga de letras minúsculas consecutivas.
Por lo tanto, imprima 3 ya que es la longitud de la subsecuencia «abc».Entrada: S = “g abbsdcdggbe”
Salida: 5
Enfoque ingenuo: el enfoque más simple es generar todas las subsecuencias posibles de la string dada y, si existe alguna subsecuencia de la string dada que tenga caracteres consecutivos y tenga una longitud máxima, imprima esa longitud.
Complejidad temporal: O(2 N )
Espacio auxiliar: O(1)
Enfoque eficiente: el enfoque anterior también se puede optimizar generando todas las subsecuencias consecutivas posibles de la string dada a partir de cada alfabeto en minúscula e imprimiendo el máximo entre todas las subsecuencias encontradas. Siga los pasos a continuación para resolver el problema:
- Inicialice una variable, digamos ans, como 0 que almacene la longitud máxima de la subsecuencia consecutiva.
- Para cada carácter ch sobre el rango [a, z] realice lo siguiente:
- Inicialice una variable cnt como 0 que almacene la longitud de una subsecuencia de caracteres consecutivos a partir de ch .
- Recorra la string dada S y si el carácter actual es ch , entonces incremente el cnt en 1 y actualice el carácter actual ch al siguiente carácter por (ch + 1) .
- Actualizar ans = max(ans, cnt)
- Después de los pasos anteriores, imprima el valor de ans como resultado.
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 length of subsequence
// starting with character ch
int findSubsequence(string S, char ch)
{
// Length of the string
int N = S.length();
// Stores the maximum length
int ans = 0;
// Traverse the given string
for (int i = 0; i < N; i++) {
// If s[i] is required
// character ch
if (S[i] == ch) {
// Increment ans by 1
ans++;
// Increment character ch
ch++;
}
}
// Return the current maximum
// length with character ch
return ans;
}
// Function to find the maximum length
// of subsequence of consecutive
// characters
int findMaxSubsequence(string S)
{
// Stores the maximum length of
// consecutive characters
int ans = 0;
for (char ch = 'a'; ch <= 'z'; ch++) {
// Update ans
ans = max(ans, findSubsequence(S, ch));
}
// Return the maximum length of
// subsequence
return ans;
}
// Driver Code
int main()
{
// Input
string S = "abcabefghijk";
// Function Call
cout << findMaxSubsequence(S);
return 0;
}
Java
// C# program for the above approach
import java.io.*;
import java.util.*;
import java.util.Arrays;
class GFG{
// Function to find the length of subsequence
// starting with character ch
static int findSubsequence(String S, char ch)
{
// Length of the string
int N = S.length();
// Stores the maximum length
int ans = 0;
// Traverse the given string
for(int i = 0; i < N; i++)
{
// If s[i] is required
// character ch
if(S.charAt(i) == ch)
{
// Increment ans by 1
ans++;
// Increment character ch
ch++;
}
}
// Return the current maximum
// length with character ch
return ans;
}
// Function to find the maximum length
// of subsequence of consecutive
// characters
static int findMaxSubsequence(String S)
{
// Stores the maximum length of
// consecutive characters
int ans = 0;
for(char ch = 'a'; ch <= 'z'; ch++)
{
// Update ans
ans = Math.max(ans, findSubsequence(S, ch));
}
// Return the maximum length of
// subsequence
return ans;
}
// Driver Code
public static void main(String[] args)
{
// Input
String S = "abcabefghijk";
// Function Call
System.out.print(findMaxSubsequence(S));
}
}
// This code is contributed by shivanisinghss2110
Python3
# Python3 program for the above approach
# Function to find the length of subsequence
# starting with character ch
def findSubsequence(S, ch):
# Length of the string
N = len(S)
# Stores the maximum length
ans = 0
# Traverse the given string
for i in range(N):
# If s[i] is required
# character ch
if (S[i] == ch):
# Increment ans by 1
ans += 1
# Increment character ch
ch=chr(ord(ch) + 1)
# Return the current maximum
# length with character ch
return ans
# Function to find the maximum length
# of subsequence of consecutive
# characters
def findMaxSubsequence(S):
#Stores the maximum length of
# consecutive characters
ans = 0
for ch in range(ord('a'),ord('z') + 1):
# Update ans
ans = max(ans, findSubsequence(S, chr(ch)))
# Return the maximum length of
# subsequence
return ans
# Driver Code
if __name__ == '__main__':
# Input
S = "abcabefghijk"
# Function Call
print (findMaxSubsequence(S))
# This code is contributed by mohit kumar 29.
C#
// C# program for the above approach
using System;
using System.Collections.Generic;
class GFG{
// Function to find the length of subsequence
// starting with character ch
static int findSubsequence(string S, char ch)
{
// Length of the string
int N = S.Length;
// Stores the maximum length
int ans = 0;
// Traverse the given string
for(int i = 0; i < N; i++)
{
// If s[i] is required
// character ch
if (S[i] == ch)
{
// Increment ans by 1
ans++;
// Increment character ch
ch++;
}
}
// Return the current maximum
// length with character ch
return ans;
}
// Function to find the maximum length
// of subsequence of consecutive
// characters
static int findMaxSubsequence(string S)
{
// Stores the maximum length of
// consecutive characters
int ans = 0;
for(char ch = 'a'; ch <= 'z'; ch++)
{
// Update ans
ans = Math.Max(ans, findSubsequence(S, ch));
}
// Return the maximum length of
// subsequence
return ans;
}
// Driver Code
public static void Main()
{
// Input
string S = "abcabefghijk";
// Function Call
Console.Write(findMaxSubsequence(S));
}
}
// This code is contributed by SURENDRA_GANGWAR
Javascript
<script>
// Javascript program for the above approach
// Function to find the length of subsequence
// starting with character ch
function findSubsequence(S,ch)
{
// Length of the string
let N = S.length;
// Stores the maximum length
let ans = 0;
// Traverse the given string
for(let i = 0; i < N; i++)
{
// If s[i] is required
// character ch
if (S[i] == ch)
{
// Increment ans by 1
ans++;
// Increment character ch
ch=String.fromCharCode(ch.charCodeAt(0)+1);
}
}
// Return the current maximum
// length with character ch
return ans;
}
// Function to find the maximum length
// of subsequence of consecutive
// characters
function findMaxSubsequence(S)
{
// Stores the maximum length of
// consecutive characters
let ans = 0;
for(let ch = 'a'.charCodeAt(0); ch <= 'z'.charCodeAt(0); ch++)
{
// Update ans
ans = Math.max(ans, findSubsequence(S, String.fromCharCode(ch)));
}
// Return the maximum length of
// subsequence
return ans;
}
// Driver Code
let S = "abcabefghijk";
// Function Call
document.write(findMaxSubsequence(S));
// This code is contributed by patel2127
</script>
Producción
7
Complejidad de Tiempo: O(26*N)
Espacio Auxiliar: O(1)
Publicación traducida automáticamente
Artículo escrito por coder_nero y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA