有序元音的最长完整子序列

Question

给定一个由“a”、“e”、“i”、“o”或“u”组成的字符串，按顺序找到最长的元音子序列。例如，如果字符串是“aeiaeiou”，那么答案是6，即子序列“aaeiou”。另一个例子是：“aeiaaioooaauuaeiou”，答案是 10。

我想出了 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)

Answer 1

O(N)，通过跟踪每个最后一个子序列元音的最大长度：

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)