Longest Ordered Subsequence of Vowels - Dynamic Pr

Question

Given a string consisting of only vowels, find the longest subsequence in the given string such that it consists of all five vowels and is a sequence of one or more a’s, followed by one or more e’s, followed by one or more i’s, followed by one or more o’s and followed by one or more u’s.

If there is more than one longest subsequence, print any one.

QUESTION: can u pls show how u would add memoization to soln below/show how to solve using dp? I've seen how to solve recursively (below). I'm asking for help in arriving at dp soln.

Examples:

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

Approach: We loop through all the characters in the string recursively and follow the given conditions:

If the subsequence is empty, we include the vowel at the current index only if it is ‘a’. Otherwise, we move on to the next index. If the vowel at the current index is same as the last vowel included in the subsequence, we include it. If the vowel at the current index is the next possible vowel (i.e a–> e–> i–> o–> u ) after the last vowel included in the subsequence, we have two options: either include it or move on to the next index. Hence we choose the one which gives the longest subsequence. If none of the above conditions is satisfied, we move on to the next index (to avoid invalid ordering of vowels in the subsequence). If we have reached the end of the string, we check if the current subsequence is valid or not. If it is valid (i.e if it contains all the vowels), we return it, else we return an empty list.

# 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) 

Output: ['a', 'e', 'i', 'i', 'o', 'o', 'o', 'u', 'u', 'u']

Answer 1

The key realization for memoizing your function is that you can use (last_chosen_char, length, index) as your memo key. In other words, treat "aaeeeiiioo", i=15 and "aaaaaaaeio", i=15 as identical, because their last chosen characters, lengths and current indices are equivalent. The subproblems of both calls will have identical solutions and we only need to bother computing one of them.

A few additional remarks:

• Avoid global variables which break encapsulation of your functions, which should work as black boxes and not have external dependencies.
• Use default parameters or a helper function to hide unnecessary parameters from the caller and offer a clean interface.
• Since lists aren't hashable (because they're mutable), I switched to using strings.
• After memoization, your call stack is the new bottleneck. You can consider using loops to collect series of duplicates. Similarly, once you've chosen a "u", you might as well loop and collect all remaining "u"s in the string; there are no more decisions to be made. You might wish to pre-process the input string a bit to prune off more of the call stack. For example, record the next char position for each index and bail early once you've hit the last "u". None of this would help the worst case, though, so rewriting the logic iteratively using a bottom-up approach would be optimal.

Putting it together, you can now input strings up to the length of the stack size:

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()

Here's an example run on a string of 900 characters:

original: uouoouiuoueaeeiiiaaaouuuueuaiaeaioaaiouaouiaiiaiuuueaueaieeueeuuouioaoaeueoioeoeioiuiaiaoeuuuuauuaiuueiieaauuoieiuoiaiueeeoaeaueaaaiaiiieuaoaiaaoiaoaueouaiiooaeeoioiaoieouuuoeaoaeeaaiuieouaeeooiiuooeauueaoaoaeuoaieauooueeeuiueuaeoeouuuiaoiauiaoiaaeeoeouuuueuiiuueoeeoiieuuuauooeuuaaaueuaaaaoaieaiiuoaoouueeeooiuoieoaueooaaioaeoiiiauuoeiaioeauaueiiaeoueioeiieuoiueoeoueeiuiooaioeooueuioaoaeoaiiiauoooieueoeauaiauauuauoueeauouieeoeoeiaeeeeooooeoaueouuuuiioeeuioueeuiaiueooeueeuuuoooeeuooeuoeeeaiioeeiioauiaeaiuaiauooiioeoeueoeieuueouaeeuuoeuaueeeauiiaoeeaeuieoeiuoooeaeeiuaiauuieouuuiuouiuieieoueiiaoiuioaiououooieiauuuououuiiiuaoeeieueeiuoeiaouoeueieuoiaeuoeiieeeaaaeiaeeoauoaoeuuoiiaaeiuiouueaoeuueeoouiaeeeouiouaaaeiouaaeauauioeoeuiauaeaououoaiuuueuieiaeeaouuueeaaiauoieoioaoiuuaioaiauioueieuuuueiaeeuaoeeoeioeoaiauiiuaouuoouooouaeueaioiaouuiiuauiaaeooeueiuoiuoeeauueuuueuueouiiauiuaoiuuoeuoeeauaeoo    
max subsequence: aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeiiiiiiiiiiiooooouuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuu

Try it!