Subsecuencia ordenada más larga de vocales

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: 

  1. Si la subsecuencia está vacía, incluimos la vocal en el índice actual solo si es ‘a’. De lo contrario, pasamos al siguiente índice.
  2. Si la vocal en el índice actual es la misma que la última vocal incluida en la subsecuencia, la incluimos.
  3. 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.
  4. 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).
  5. 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

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *