Dada una string que consta solo de vocales, encuentre la subsecuencia más larga en la string dada de modo que conste de las cinco vocales y sea una secuencia de una o más a, seguidas de una o más e, seguidas de una o más i, seguidas de uno o más os y seguido por uno o más ues.
Si hay más de una subsecuencia más larga, imprima cualquiera.
Ejemplos:
Input : str = "aeiaaioooaauuaeiou"
Output : {a, a, a, a, a, a, e, i, o, u}
There are two possible outputs in this case:
{a, a, a, a, a, a, e, i, o, u} and,
{a, e, i, i, o, o, o, u, u, u}
each of length 10
Input : str = "aaauuiieeou"
Output : No subsequence possible
Enfoque:
recorremos todos los caracteres de la string de forma recursiva y seguimos las condiciones dadas:
- Si la subsecuencia está vacía, incluimos la vocal en el índice actual solo si es ‘a’. De lo contrario, pasamos al siguiente índice.
- Si la vocal en el índice actual es la misma que la última vocal incluida en la subsecuencia, la incluimos.
- Si la vocal en el índice actual es la siguiente vocal posible (es decir, a–> e–> i–> o–> u ) después de la última vocal incluida en la subsecuencia, tenemos dos opciones: incluirla o pasar a la siguiente. índice siguiente. Por lo tanto, elegimos el que da la subsecuencia más larga.
- Si no se cumple ninguna de las condiciones anteriores, pasamos al siguiente índice (para evitar un orden inválido de las vocales en la subsecuencia).
- Si hemos llegado al final de la string, comprobamos si la subsecuencia actual es válida o no. Si es válido (es decir, si contiene todas las vocales), lo devolvemos, de lo contrario, devolvemos una lista vacía.
Método 1
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program to find the longest subsequence
// of vowels in the specified order
#include <bits/stdc++.h>
using namespace std;
vector<char> vowels = { 'a', 'e', 'i', 'o', 'u' };
// Mapping values for vowels
map<char, int> mapping = { { 'a', 0 }, { 'e', 1 },
{ 'i', 2 }, { 'o', 3 },
{ 'u', 4 } };
// Function to check if given subsequence
// contains all the vowels or not
bool isValidSequence(string subList)
{
for(char c : vowels)
{
// not contain vowel
if (subList.find(c) == std::string::npos)
return 0;
}
return 1;
}
// Function to find the longest subsequence
// of vowels in the given string in specified
// order
string longestSubsequence(string str,
string subList,
int index)
{
// If we have reached the end of the
// string, return the subsequence
// if it is valid, else return an
// empty list
int len = str.length();
if (index >= len)
{
if (isValidSequence(subList))
return subList;
else
return "";
}
// If there is no vowel in the
// subsequence yet, add vowel
// at current index if it is 'a',
// else move on to the next character
// in the string
else if (subList.size() == 0)
{
if (str[index] != 'a')
return longestSubsequence(
str, "", index + 1);
else
return longestSubsequence(
str, subList + str[index],
index + 1);
}
// If the last vowel in the subsequence
// until now is same as the vowel at
// current index, add it to the subsequence
else if (mapping[subList[subList.size() - 1]] ==
mapping[str[index]])
return longestSubsequence(
str, subList+str[index], index + 1);
// If the vowel at the current index comes
// right after the last vowel in the
// subsequence, we have two options:
// either to add the vowel in the
// subsequence, or move on to next character.
// We choose the one which gives the longest
// subsequence.
else if (mapping[subList[subList.size() - 1]] + 1 ==
mapping[str[index]])
{
string sub1 = longestSubsequence(
str, subList + str[index], index + 1);
string sub2 = longestSubsequence(
str, subList, index + 1);
if (sub1.length() > sub2.length())
return sub1;
else
return sub2;
}
else
return longestSubsequence(
str, subList, index + 1);
}
// Driver Code
int main()
{
string str= "aeiaaioooauuaeiou";
string subsequence = longestSubsequence(
str, "", 0);
if (subsequence.length() == 0)
cout << "No subsequence possible\n";
else
cout << subsequence << "\n";
}
// This code is contributed by ajaykr00kj
Java
// Java program to find the longest subsequence
// of vowels in the specified order
import java.util.*;
public class Main
{
static Vector<Character> vowels = new Vector<Character>();
// Mapping values for vowels
static HashMap<Character, Integer> mapping = new HashMap<Character, Integer>();
// Function to check if given subsequence
// contains all the vowels or not
static boolean isValidSequence(String subList)
{
for(char c : vowels)
{
// not contain vowel
if (subList.indexOf(c) < 0)
return false;
}
return true;
}
// Function to find the longest subsequence
// of vowels in the given string in specified
// order
static String longestSubsequence(String str, String subList, int index)
{
// If we have reached the end of the
// string, return the subsequence
// if it is valid, else return an
// empty list
int len = str.length();
if (index >= len)
{
if (isValidSequence(subList))
return subList;
else
return "";
}
// If there is no vowel in the
// subsequence yet, add vowel
// at current index if it is 'a',
// else move on to the next character
// in the string
else if (subList.length() == 0)
{
if (str.charAt(index) != 'a')
return longestSubsequence(str, "", index + 1);
else
return longestSubsequence(str, subList + str.charAt(index), index + 1);
}
// If the last vowel in the subsequence
// until now is same as the vowel at
// current index, add it to the subsequence
else if (mapping.get(subList.charAt(subList.length() - 1)) ==
mapping.get(str.charAt(index)))
return longestSubsequence(str, subList+str.charAt(index), index + 1);
// If the vowel at the current index comes
// right after the last vowel in the
// subsequence, we have two options:
// either to add the vowel in the
// subsequence, or move on to next character.
// We choose the one which gives the longest
// subsequence.
else if (mapping.get(subList.charAt(subList.length() - 1)) + 1 ==
mapping.get(str.charAt(index)))
{
String sub1 = longestSubsequence(
str, subList + str.charAt(index), index + 1);
String sub2 = longestSubsequence(
str, subList, index + 1);
if (sub1.length() > sub2.length())
return sub1;
else
return sub2;
}
else
return longestSubsequence(
str, subList, index + 1);
}
public static void main(String[] args) {
mapping.put('a', 0);
mapping.put('e', 1);
mapping.put('i', 2);
mapping.put('o', 3);
mapping.put('u', 4);
vowels.add('a');
vowels.add('e');
vowels.add('i');
vowels.add('o');
vowels.add('u');
String str= "aeiaaioooauuaeiou";
String subsequence = longestSubsequence(str, "", 0);
if (subsequence.length() == 0)
System.out.println("No subsequence possible");
else
{
System.out.print("[");
for(int i = 0; i < subsequence.length() - 1; i++)
{
System.out.print("'" + subsequence.charAt(i) + "'" + ", ");
}
System.out.print("'" + subsequence.charAt(subsequence.length()-1) + "'" + "]");
}
}
}
// This code is contributed by mukesh07.
Python3
# Python3 program to find the longest subsequence
# of vowels in the specified order
vowels = ['a', 'e', 'i', 'o', 'u']
# Mapping values for vowels
mapping = {'a': 0, 'e': 1, 'i': 2, 'o': 3, 'u': 4}
# Function to check if given subsequence
# contains all the vowels or not
def isValidSequence(subList):
for vowel in vowels:
if vowel not in subList:
return False
return True
# Function to find the longest subsequence of vowels
# in the given string in specified order
def longestSubsequence(string, subList, index):
# If we have reached the end of the string,
# return the subsequence
# if it is valid, else return an empty list
if index == len(string):
if isValidSequence(subList) == True:
return subList
else:
return []
else:
# If there is no vowel in the subsequence yet,
# add vowel at current index if it is 'a',
# else move on to the next character
# in the string
if len(subList) == 0:
if string[index] != 'a':
return longestSubsequence(string, subList, index + 1)
else:
return longestSubsequence(string, subList + \
[string[index]], index + 1)
# If the last vowel in the subsequence until
# now is same as the vowel at current index,
# add it to the subsequence
elif mapping[subList[-1]] == mapping[string[index]]:
return longestSubsequence(string, subList + \
[string[index]], index + 1)
# If the vowel at the current index comes
# right after the last vowel
# in the subsequence, we have two options:
# either to add the vowel in
# the subsequence, or move on to next character.
# We choose the one which gives the longest subsequence.
elif (mapping[subList[-1]] + 1) == mapping[string[index]]:
sub1 = longestSubsequence(string, subList + \
[string[index]], index + 1)
sub2 = longestSubsequence(string, subList, index + 1)
if len(sub1) > len(sub2):
return sub1
else:
return sub2
else:
return longestSubsequence(string, subList, index + 1)
# Driver Code
if __name__ == "__main__":
string = "aeiaaioooauuaeiou"
subsequence = longestSubsequence(string, [], 0)
if len(subsequence) == 0:
print("No subsequence possible")
else:
print(subsequence)
C#
// C# program to find the longest subsequence
// of vowels in the specified order
using System;
using System.Collections.Generic;
class GFG {
static List<char> vowels = new List<char>(new char[]{'a', 'e', 'i', 'o', 'u'});
// Mapping values for vowels
static Dictionary<char, int> mapping = new Dictionary<char, int>();
// Function to check if given subsequence
// contains all the vowels or not
static bool isValidSequence(string subList)
{
foreach(char c in vowels)
{
// not contain vowel
if (subList.IndexOf(c) < 0)
return false;
}
return true;
}
// Function to find the longest subsequence
// of vowels in the given string in specified
// order
static string longestSubsequence(string str,
string subList,
int index)
{
// If we have reached the end of the
// string, return the subsequence
// if it is valid, else return an
// empty list
int len = str.Length;
if (index >= len)
{
if (isValidSequence(subList))
return subList;
else
return "";
}
// If there is no vowel in the
// subsequence yet, add vowel
// at current index if it is 'a',
// else move on to the next character
// in the string
else if (subList.Length == 0)
{
if (str[index] != 'a')
return longestSubsequence(
str, "", index + 1);
else
return longestSubsequence(
str, subList + str[index],
index + 1);
}
// If the last vowel in the subsequence
// until now is same as the vowel at
// current index, add it to the subsequence
else if (mapping[subList[subList.Length - 1]] ==
mapping[str[index]])
return longestSubsequence(
str, subList+str[index], index + 1);
// If the vowel at the current index comes
// right after the last vowel in the
// subsequence, we have two options:
// either to add the vowel in the
// subsequence, or move on to next character.
// We choose the one which gives the longest
// subsequence.
else if (mapping[subList[subList.Length - 1]] + 1 ==
mapping[str[index]])
{
string sub1 = longestSubsequence(
str, subList + str[index], index + 1);
string sub2 = longestSubsequence(
str, subList, index + 1);
if (sub1.Length > sub2.Length)
return sub1;
else
return sub2;
}
else
return longestSubsequence(
str, subList, index + 1);
}
static void Main() {
mapping['a'] = 0;
mapping['e'] = 1;
mapping['i'] = 2;
mapping['o'] = 3;
mapping['u'] = 4;
string str= "aeiaaioooauuaeiou";
string subsequence = longestSubsequence(str, "", 0);
if (subsequence.Length == 0)
Console.Write("No subsequence possible");
else
{
Console.Write("[");
for(int i = 0; i < subsequence.Length - 1; i++)
{
Console.Write("'" + subsequence[i] + "'" + ", ");
}
Console.Write("'" + subsequence[subsequence.Length-1] + "'" + "]");
}
}
}
// This code is contributed by divyeshrabadiya07.
Javascript
<script>
// Javascript program to find the longest subsequence
// of vowels in the specified order
let vowels = [ 'a', 'e', 'i', 'o', 'u' ];
// Mapping values for vowels
let mapping = new Map();
mapping['a'] = 0;
mapping['e'] = 1;
mapping['i'] = 2;
mapping['o'] = 3;
mapping['u'] = 4;
// Function to check if given subsequence
// contains all the vowels or not
function isValidSequence(subList)
{
for(let c = 0; c < vowels.length; c++)
{
// not contain vowel
if (!subList.includes(vowels))
return false;
}
return true;
}
// Function to find the longest subsequence
// of vowels in the given string in specified
// order
function longestSubsequence(str, subList, index)
{
// If we have reached the end of the
// string, return the subsequence
// if it is valid, else return an
// empty list
let len = str.length;
if (index >= len)
{
if (isValidSequence(subList))
return subList;
else
return "";
}
// If there is no vowel in the
// subsequence yet, add vowel
// at current index if it is 'a',
// else move on to the next character
// in the string
else if (subList.length == 0)
{
if (str[index] != 'a')
return longestSubsequence(str, "", index + 1);
else
return longestSubsequence(str, subList + str[index], index + 1);
}
// If the last vowel in the subsequence
// until now is same as the vowel at
// current index, add it to the subsequence
else if (mapping[subList[subList.length - 1]] == mapping[str[index]])
return longestSubsequence(str, subList+str[index], index + 1);
// If the vowel at the current index comes
// right after the last vowel in the
// subsequence, we have two options:
// either to add the vowel in the
// subsequence, or move on to next character.
// We choose the one which gives the longest
// subsequence.
else if (mapping[subList[subList.length - 1]] + 1 == mapping[str[index]])
{
let sub1 = longestSubsequence(
str, subList + str[index], index + 1);
let sub2 = longestSubsequence(
str, subList, index + 1);
if (sub1.length > sub2.length)
return sub1;
else
return sub2;
}
else
return longestSubsequence(str, subList, index + 1);
}
let str= "aeiaaioooauuaeiou";
let subsequence = longestSubsequence(str, "", 0);
if (subsequence.length == 0)
document.write("No subsequence possible");
else
{
document.write("[")
for(let i = 0; i < subsequence.length - 1; i++)
{
document.write("'" + subsequence[i] + "'" + ", ");
}
document.write("'" + subsequence[subsequence.length-1] + "'" + "]");
}
// This code is contributed by decode2207.
</script>
Producción
aeiiooouuu
Método 2 (Programación Dinámica)
Python3
from random import choice
def longest_subsequence(string):
def helper(chosen="", i=0):
if i == len(string):
return chosen if set("aeiou").issubset(set(chosen)) else ""
hashable = (chosen[-1] if chosen else None, len(chosen), i)
if hashable in memo:
return memo[hashable]
if not chosen:
res = helper("a" if string[i] == "a" else chosen, i + 1)
elif chosen[-1] == string[i]:
res = helper(chosen + string[i], i + 1)
elif mapping[chosen[-1]] + 1 == mapping[string[i]]:
sub1 = helper(chosen + string[i], i + 1)
sub2 = helper(chosen, i + 1)
res = sub1 if len(sub1) > len(sub2) else sub2
else:
res = helper(chosen, i + 1)
memo[hashable] = res
return res
mapping = {x: i for i, x in enumerate("aeiou")}
memo = {}
return helper()
if __name__ == "__main__":
tests = [
"aeiaaioooaauuaeiou",
"aaauuiieeou",
"".join(choice("aeiou") for _ in range(40)),
"".join(choice("aeiou") for _ in range(900))
]
for string in tests:
print("original:", string)
subsequence = longest_subsequence(string)
if subsequence:
print("\nmax subsequence:", "".join(subsequence))
else:
print("No subsequence possible")
print("-" * 40, "\n")
Producción
original: aeiaaioooaauuaeiou max subsequence: aaaaaaeiou ---------------------------------------- original: aaauuiieeou No subsequence possible ---------------------------------------- original: uioeaieauaiuoaaauueaaouaaeeioeuauuieaiio max subsequence: aaaaaaaaaaeeiouuu ---------------------------------------- original: aaauauiieuaeaeeaaouaiauaiouoeaeaeiuuaiooaioeueiuuieaoaueuoeooeeoiiouaueaiauauooeuauuuuooaooieiuaeooueuuuooiiaaaeiaioeioiiuueieieaiaeuoiioaoieuooaaooaiuioeauieeeaeauiauoeueiaeeeooiaeoauioiuoaoaauuuueeaeuaaeiuaeiioaeaoiuaieaoioioiuoeeuouoiuaiuuaeioeoueaaoieaauoaeuaeiioieuoaiiiaeieiaueaaoeiiuuaoaiieoaioaeuouaeaouioeaauoiaiioeuiooeeeoiaeouuauuieeoooauueeuioiuaieuauaaeaeoaiooeaaoaiuouiuauauoaueeeuaeaioiooooaeeeoaaeaaeoaaiuaooooauiaiauaeuiueuiuoiieoeouiaueioioeeueieeaaieieuaaiuoeuiuouaeuiaiauoauuieuooaiouoeeaaoiaouoaaeiaiaiuuaeiiiaeuaiiouaiuuoiooiieoiiaiuoaueeiueoeeuauieoaauaeeiieioiiooaiiuaaeeoaoioauiouueoieaaaeueuuioeeauauaeuooooaiaeieaiieaaiaeeoeuiuaaeaiueaeiioaaeiooaouiaueeaoueueeeieuueaeoueaeaoiooiuioaoeaeaiuuoaeauoeeieeiuaiaaeauaauaiiuaauiiooioiuuauauuaouooeoeouioeoeoioaioieeuuuauuoouiaeueoiioaoeaoeaieeuouoeeouuoeioieuiaeioieieeeouiiueieeioeeuuaioeeoaaiaiooieeioiiouuaaoueueuaoaiaaeeeoouo max subsequence: aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaeeeeeeeeeeeeeeeeeeiiiiiiooooooooooooooooooooooooooooooooouuuuuu ----------------------------------------
Complejidad temporal: O(m*n).
Espacio Auxiliar: O(m*n).
Enfoque alternativo (programación dinámica)
1. Este enfoque es similar a encontrar el concepto de subsecuencia creciente más larga.
2. Mantenemos dos arreglos
(i) dp que almacena la Subsecuencia Ordenada más larga que termina en el índice i
(ii) padre que almacena el índice del carácter anterior del carácter actual en la secuencia de vocales {a->e->i->o->u}
3. Para cada índice i, encontramos el valor máximo de dp[j] (0 <= j <i) donde s[j] es el carácter anterior de s[i] (carácter anterior en la secuencia de vocales) y parent[i] será ser j.
Implementación del enfoque anterior:
C++
#include <bits/stdc++.h>
using namespace std;
char getPrevChar(char c)
{
// previous characters in the order {a -> e -> i -> o ->
// u}
// previous of 'a' is 'a' (since 'a' can be placed
// after 'a')
if (c == 'a')
return 'a';
if (c == 'e')
return 'a';
if (c == 'i')
return 'e';
if (c == 'o')
return 'i';
else
return 'o';
}
int main()
{
string s = "aeiaaioooaauuaeiou";
int n = s.length();
vector<int> parent(n);
// parent[i] ---> stores the previous character's index
// to which it can be added
for (int i = 0; i < n; i++) {
parent[i] = i;
// initial parent is itself
}
vector<int> dp(n, 0);
// dp[i] ----> length of longest sequence ending at
// index i;
int ind = -1;
for (int i = 0; i < n; i++) {
if (s[i] == 'a') {
dp[i] = 1;
ind = i;
break;
}
}
// if there is no 'a'
if (ind == -1) {
cout << "NO POSSIBLE SEQUENCE" << endl;
}
// iterating from next character (after 'a')
for (int i = ind + 1; i < n; i++) {
int prev = getPrevChar(s[i]);
// previous character of the current character in
// vowel sequence {a -> e -> i -> o -> u}
int cur = dp[i];
int par = i;
for (int j = 0; j < i; j++) {
if (s[j] == prev || s[j] == s[i]) {
// if it matches its prev char or itself
// then we can add to it if its length is
// maximum than previous
if (cur <= dp[j] + 1) {
cur = dp[j] + 1;
par = j;
}
}
}
dp[i] = max(cur, 1);
parent[i] = par;
}
int lastIndex = -1;
// finding the last occurrence of 'u' which will be last
// occurrence of the sequence
for (int i = n - 1; i >= 0; i--) {
if (s[i] == 'u') {
lastIndex = i;
break;
}
}
// if we do not find 'u'
if (lastIndex == -1) {
cout << "NO POSSIBLE SEQUENCE" << endl;
exit(0);
}
string res = "";
while (lastIndex != parent[lastIndex]) {
res += s[lastIndex];
lastIndex = parent[lastIndex];
}
res += s[lastIndex];
// adding first character in the subsequence (which has
// the parent as its index)
if (s[lastIndex] != 'a') {
cout << "NO POSSIBLE SEQUENCE" << endl;
exit(0);
}
// reversing the string because we added from the last
reverse(res.begin(), res.end());
cout << res << endl;
return 0;
}
Producción
aaaaaaeiou
Complejidad temporal: O(m*n).
Espacio Auxiliar: O(m*n).
Publicación traducida automáticamente
Artículo escrito por rituraj_jain y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA