Python Program for longest ordered subsequence of vowels

In this tutorial, we are going to write a Python program to get the longest ordered subsequence of vowels.

Input: “aaeeiaaiieiou”

Output: [‘a’, ‘a’, ‘e’, ‘e’, ‘i’, ‘i’, ‘i’, ‘i’, ‘o’, ‘u’]

Input: “aeiaeeeioouuu”

Output: [‘a’, ‘a’, ‘e’, ‘e’, ‘e’, ‘i’, ‘o’, ‘o’, ‘u’, ‘u’, ‘u’]

Input: “aaaaaiiieeiiaaaoo”

Output: No subsequence possible

Here our aim is to find the longest subsequence of vowels in the given string of vowels in the specified order. We can specify the vowels in any order. Here we take it as:
[‘a’, ‘e’, ‘i’, ‘o’, ‘u’]

The order is up to our choice.

So, the procedure of finding this, First we will consider an empty subsequence. Then, we will start from the element at index zero in the given string. If the vowel at the current index is ‘a’, we will add it, as it is the first letter in our given order. Otherwise, we won’t add the vowel to the subsequence. Then the index increased by one. If the vowel at this index is the same as the last added vowel in subsequence, we will add the element to the sequence. We look to the element at the next index. If the vowel is the next element in the chosen order  [‘a’, ‘e’, ‘i’, ‘o’, ‘u’],
We have two choices,

We can add that vowel to the subsequence or we can move to the next vowel in the string. The best choice is taken inorder to get the largest subsequence.

In this manner, we move the index till it reaches the end of the string. When the index reaches the end, we will check whether the length of the subsequence is zero or not. Also, the validity of the formed of the subsequence is checked, ie,  whether the subsequence contains all the vowels. If the subsequence is valid we print it, else we will print “No subsequence possible”.

Sample program:

# Python program to find the longest subsequence of vowels in the specified order in the given string
vowels = ['a', 'e', 'i', 'o', 'u'] 
order= {'a': 0, 'e': 1, 'i': 2, 'o': 3, 'u': 4} # Specifying the order of vowels.

def isValidSequence(subList): # validating whether the sub list is empty or not

    for v in vowels: 
        if v not in subList: 
            return False

    return True

# Function to find the longest subsequence of vowels 
def longestSubsequence(string, subList, index): 
 
    if index == len(string):   # checking the index reached at the end of the string
        if isValidSequence(subList) == True: 
            return subList 
        else: 
            return [] 

    else: 

        if len(subList) == 0: 

            if string[index] != 'a': 
                return longestSubsequence(string, subList, index + 1)
            else: 
                return longestSubsequence(string, subList + [string[index]], index + 1)
                             

         
        elif order[subList[-1]] == order[string[index]]: 
            return longestSubsequence(string, subList + [string[index]], index + 1)
                             


        elif (order[subList[-1]] + 1) == order[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) 

# main code
if __name__ == "__main__": 

    string = "aaeeiaaiieiou"

    subsequence = longestSubsequence(string, [], 0) 
    if len(subsequence) == 0: 
        print("No subsequence possible") 
    else: 
        print(subsequence)

Output: [‘a’, ‘a’, ‘e’, ‘e’, ‘i’, ‘i’, ‘i’, ‘i’, ‘o’, ‘u’]