Given a string made up of "a", "e", "i", "o", or "u", find the longest subsequence of vowels in order. For example, is the string is "aeiaeiou", then the answer is 6, making the subsequence "aaeiou". Another example is: "aeiaaioooaauuaeiou" where the answer is 10. A complete subsequence means that you need to have all the vowels in order, a -> e -> i -> o -> u, but you can have repeats of vowels like "aaeeeeiiooouuu" is valid. If no such subsequence exists, return 0.
I came up with a DP approach of O(n^2) and I'm curious if there is a faster version for this problem.
def find_longest_dp(vowels):
n = len(vowels)
dp = [[0, False] for _ in range(n)]
prev_vowel = {"a": None, "e": "a", "i": "e", "o": "i", "u": "o"}
for i in range(n):
if vowels[i] == "a":
dp[i] = [1, True]
for j in range(i):
if dp[j][1] and vowels[j] in {vowels[i], prev_vowel[vowels[i]]}:
dp[i][0] = max(dp[i][0], dp[j][0] + 1)
dp[i][1] = True
return max((dp[i][0] for i in range(n) if vowels[i] == 'u'), default=0)
O(n) by keeping track of the max length for each last-of-the-subsequence vowel (e.g., maxlen[3] tells the max length of an ordered subsequence ending with 'o'):
def find_longest_dp2(vowels):
maxlen = [0] * 5
for v in vowels:
i = 'aeiou'.find(v)
maxlen[i] = max(maxlen[:i+1]) + 1
return max(maxlen)
Or if all five vowels need to be in the subsequence (as the "complete" in your title suggests) and you want 0 if no such subsequence exists (as your code suggests):
def find_longest_dp3(vowels):
maxlen = [0] + [float('-inf')] * 5
for v in vowels:
i = '.aeiou'.find(v)
maxlen[i] = max(maxlen[i-1:i+1]) + 1
return max(maxlen[5], 0)
Attempt This Online! with testing.