Dada uma sequência composta de "a", "e", "i", "o" ou "u", encontre a maior subsequência de vogais em ordem. Por exemplo, se a sequência for "aeiaeiou", então a resposta é 6, tornando a subsequência "aaeiou". Outro exemplo é: "aeiaaioooaauuaeiou" onde a resposta é 10. Uma subsequência completa significa que você precisa ter todas as vogais em ordem, a -> e -> i -> o -> u, mas você pode ter repetições de vogais como "aaeeeeiiooouuu" é válido. Se nenhuma subsequência existir, retorne 0.
Eu criei uma abordagem DP de O(n^2) e estou curioso para saber se existe uma versão mais rápida para esse problema.
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)