John Doe's questions

给定一个由“a”、“e”、“i”、“o”或“u”组成的字符串，按顺序找到最长的元音子序列。例如，如果字符串是“aeiaeiou”，则答案是 6，从而得到子序列“aaeiou”。另一个示例是：“aeiaaioooaauuaeiou”，其答案是 10。完整的子序列意味着您需要按顺序排列所有元音，a -> e -> i -> o -> u，但您可以重复元音，例如“aaeeeeiiooouuu”是有效的。如果不存在这样的子序列，则返回 0。

我想到了一个 O(n^2) 的 DP 方法，我很好奇是否有更快的版本可以解决这个问题。

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)