Subsecuencia más larga que consta de vocales y consonantes alternas

Dada una string S no vacía , la tarea es imprimir la subsecuencia más larga de la string S que contiene vocales y consonantes alternas. 
Nota: Si existen múltiples subsecuencias de la misma longitud, imprima la subsecuencia que tenga la suma máxima de valores ASCII de sus caracteres.
Ejemplos: 

Entrada: S = “geeksforgeeks” 
Salida: gesores 
Explicación: “gekorek”, “gekores”, “gekogek”, “gekoges”, “gesorek”, “gesores”, “gesogek”, “gesoges”, “geforek”, “gefores ”, “gefogek” y “gefoges” son las posibles subsecuencias más largas con consonantes y vocales alternas. “gesores” es la subsecuencia con máxima suma de valores ASCII de caracteres y por lo tanto es la solución.

Entrada: S = “ababababab” 
Salida: ababababab 
Explicación: “ababababab” es la subsecuencia más larga posible que contiene alternancia de vocales y consonantes. 

Enfoque: 
siga los pasos a continuación para resolver el problema: 

• Almacene el valor ASCII del primer carácter de S como el máximo del bloque actual ( maxi ) y escriba el carácter en flag . Si el carácter es consonante, establezca la bandera como 0 y 1 de lo contrario.
• Atraviesa el resto de la cuerda.
• Para cada carácter, compruebe si pertenece al mismo bloque que el carácter anterior o no.
• Si pertenece al mismo bloque, actualice maxi a max (maxi, valor ASCII del i ^-ésimo carácter).
• De lo contrario, agregue el carácter con valor ASCII maxi a la respuesta. Almacene el valor ASCII del i ^-ésimo carácter actual como maxi . Actualice la bandera a (bandera + 1)%2 para indicar el tipo del carácter actual.
• Después de atravesar toda la string, agregue el carácter con valor ASCII maxi a la respuesta. Imprime la string final que representa la subsecuencia.

El siguiente código es la implementación del enfoque anterior:
 

// C++ program to find the longest
// subsequence containing alternating
// vowels and consonants
#include <bits/stdc++.h>
using namespace std;
 
// Function that return 1 or 0
// if the given character is
// vowel or consonant respectively
int isVowel(char c)
{
     
    // Returns 1 if c is vowel
    if (c == 'a' || c == 'e' ||
        c == 'i' || c == 'o' ||
        c == 'u')
        return 1;
 
    // Returns 0 if
    // c is consonant
    return 0;
}
 
// Function to find the longest
// subsequence containing
// alternate vowels and
// consonants
string Subsequence(string str)
{
     
    // Store the length
    // of the string
    int n = str.length();
 
    // Assume first character
    // to be consonant
    int flag = 0;
     
    // If first character is vowel
    if (isVowel(str[0]) == 1)
        flag = 1;
         
    // Store the ASCII value
    int maxi = (int)str[0];
     
    // Stores the final answer
    string ans = "";
    for(int i = 1; i < n; i++)
    {
         
        // If the current character belongs
        // to same category (Vowel / Consonant)
        // as the previous character
        if (isVowel(str[i]) == flag)
        {
             
            // Store the maximum ASCII value
            maxi = max(maxi, (int)str[i]);
        }
         
        // Otherwise
        else
        {
             
            // Store the character with
            // maximum ASCII value from
            // the previous block
            ans += (char)(maxi);
             
            // Store the ASCII of the
            // current character as the
            // maximum of the current block
            maxi = (int)str[i];
             
            // Switch the type of the
            // current block
            flag = (flag + 1) % 2;
        }
    }
     
    // Store the character with
    // maximum ASCII value
    // from the last block
    ans += (char)(maxi);
 
    // Return the result
    return ans;
}
 
// Driver code
int main()
{
    string str = "geeksforgeeks";
     
    cout << (Subsequence(str));
}
 
// This code is contributed by chitranayal

// Java program to find the longest
// subsequence containing alternating
// vowels and consonants
import java.util.*;
import java.lang.*;
import java.io.*;
import java.math.*;
 
class GFG {
 
    // Function that return 1 or 0
    // if the given character is
    // vowel or consonant respectively
    static int isVowel(char c)
    {
        // Returns 1 if c is vowel
        if (c == 'a' || c == 'e'
            || c == 'i' || c == 'o'
            || c == 'u')
            return 1;
 
        // Returns 0 if
        // c is consonant
        return 0;
    }
 
    // Function to find the longest
    // subsequence containing
    // alternate vowels and
    // consonants
    static String Subsequence(String str)
    {
        // Store the length
        // of the string
        int n = str.length();
 
        // Assume first character
        // to be consonant
        int flag = 0;
        // If first character is vowel
        if (isVowel(str.charAt(0)) == 1)
            flag = 1;
        // Store the ASCII value
        int maxi = (int)str.charAt(0);
        // Stores the final answer
        String ans = "";
        for (int i = 1; i < n; i++) {
            // If the current character belongs
            // to same category (Vowel / Consonant)
            // as the previous character
            if (isVowel(str.charAt(i)) == flag) {
                // Store the maximum ASCII value
                maxi = Math.max(maxi,
                                (int)str.charAt(i));
            }
            // Otherwise
            else {
                // Store the character with
                // maximum ASCII value from
                // the previous block
                ans += (char)(maxi);
                // Store the ASCII of the
                // current character as the
                // maximum of the current block
                maxi = (int)str.charAt(i);
                // Switch the type of the
                // current block
                flag = (flag + 1) % 2;
            }
        }
        // Store the character with
        // maximum ASCII value
        // from the last block
        ans += (char)(maxi);
 
        // Return the result
        return ans;
    }
 
    // Driver Program
    public static void main(String[] args)
    {
        String str = "geeksforgeeks";
        System.out.println(Subsequence(str));
    }
}

# Python3 program to find the longest
# subsequence containing alternating
# vowels and consonants
 
def isVowel(c):
   
    # boolean function that check whether
    # the given char is vowel or not
    # and returns a boolean value respectively
    vowels=['a','e','i','o','u']
    if(c in vowels):
        return True
    return False
def Subsequence(str):
   
    #string that stores the final result
    ans=''
    flag=(isVowel(str[0]))
     
    #taking the first character
    #as the maximum ASCII valued char
    maxi=ord(str[0])
    for i in range(1,len(str)):
       
        # If the current character belongs to
        # same category(Vowel / Consonant) as the
        # previous character
        if (isVowel(str[i]) == flag):
           
            # choosing a maximum ASCII valued char
            maxi=max(maxi,ord(str[i]))
             
        #otherwise
        else:
            ans=ans+chr(maxi)
            maxi=ord(str[i])
             
            #toggling the flag
            flag=not(flag)
             
    #adding the last char to the answer
    ans=ans+chr(maxi)
    return ans
   
#Driver program
if __name__ == "__main__":
    input_string ='geeksforgeeks'
    print(Subsequence(input_string))
     
# Contributed by
# Nvss Maneesh Gupta

// C# program to find the longest
// subsequence containing alternating
// vowels and consonants
using System;
 
class GFG{
 
// Function that return 1 or 0
// if the given character is
// vowel or consonant respectively
static int isVowel(char c)
{
     
    // Returns 1 if c is vowel
    if (c == 'a' || c == 'e' ||
        c == 'i' || c == 'o' ||
        c == 'u')
        return 1;
 
    // Returns 0 if
    // c is consonant
    return 0;
}
 
// Function to find the longest
// subsequence containing
// alternate vowels and
// consonants
static String Subsequence(String str)
{
     
    // Store the length
    // of the string
    int n = str.Length;
 
    // Assume first character
    // to be consonant
    int flag = 0;
     
    // If first character is vowel
    if (isVowel(str[0]) == 1)
        flag = 1;
     
    // Store the ASCII value
    int maxi = (int)str[0];
     
    // Stores the readonly answer
    String ans = "";
     
    for(int i = 1; i < n; i++)
    {
         
    // If the current character belongs
    // to same category (Vowel / Consonant)
    // as the previous character
    if (isVowel(str[i]) == flag)
    {
             
        // Store the maximum ASCII value
        maxi = Math.Max(maxi, (int)str[i]);
    }
         
    // Otherwise
    else
    {
             
        // Store the character with
        // maximum ASCII value from
        // the previous block
        ans += (char)(maxi);
             
        // Store the ASCII of the
        // current character as the
        // maximum of the current block
        maxi = (int)str[i];
             
        // Switch the type of the
        // current block
        flag = (flag + 1) % 2;
    }
    }
     
    // Store the character with
    // maximum ASCII value
    // from the last block
    ans += (char)(maxi);
 
    // Return the result
    return ans;
}
 
// Driver code
public static void Main(String[] args)
{
    String str = "geeksforgeeks";
     
    Console.WriteLine(Subsequence(str));
}
}
 
// This code is contributed by 29AjayKumar

<script>
 
// Javascript program to find the longest
// subsequence containing alternating
// vowels and consonants
 
// Function that return 1 or 0
// if the given character is
// vowel or consonant respectively
function isVowel(c)
{
     
    // Returns 1 if c is vowel
    if (c == 'a' || c == 'e' ||
        c == 'i' || c == 'o' ||
        c == 'u')
        return 1;
 
    // Returns 0 if
    // c is consonant
    return 0;
}
 
// Function to find the longest
// subsequence containing
// alternate vowels and
// consonants
function Subsequence(str)
{
     
    // Store the length
    // of the string
    var n = str.length;
 
    // Assume first character
    // to be consonant
    var flag = 0;
     
    // If first character is vowel
    if (isVowel(str[0]) == 1)
        flag = 1;
         
    // Store the ASCII value
    var maxi = (str[0].charCodeAt(0));
     
    // Stores the final answer
    var ans = "";
    for(var i = 1; i < n; i++)
    {
         
        // If the current character belongs
        // to same category (Vowel / Consonant)
        // as the previous character
        if (isVowel(str[i]) == flag)
        {
             
            // Store the maximum ASCII value
            maxi = Math.max(maxi, str[i].charCodeAt(0));
        }
         
        // Otherwise
        else
        {
             
            // Store the character with
            // maximum ASCII value from
            // the previous block
            ans += String.fromCharCode(maxi);
             
            // Store the ASCII of the
            // current character as the
            // maximum of the current block
            maxi = str[i].charCodeAt(0);
             
            // Switch the type of the
            // current block
            flag = (flag + 1) % 2;
        }
    }
     
    // Store the character with
    // maximum ASCII value
    // from the last block
    ans += String.fromCharCode(maxi);
 
    // Return the result
    return ans;
}
 
// Driver code
var str = "geeksforgeeks";
document.write(Subsequence(str));
 
// This code is contributed by rrrtnx.
</script>

gesores

Complejidad de tiempo: O(N)