如何用Python查找字符串中含所有元音的最长有序子序列

需要找出给定字符串中包含所有元音（a、e、i、o、u）的最长子序列长度，规则如下：

• 元音必须按a→e→i→o→u的顺序排列，不可打乱顺序
• 元音允许重复出现

示例 #

• 字符串aeiaaioaaaaeiiiiouuuooaauuaeiu应返回13，最长有效子序列为aaaaeiiiiouuu，长度为13
• 字符串aeiooou应返回7，最长有效子序列为字符串本身
• 字符串aaeeiioouu应返回10，最长有效子序列为字符串本身
• 字符串aeiaaiooaauua应返回0，因为该字符串未按顺序包含所有元音

现有实现代码 #

def normalize_string(s):
    normalized = []
    previous_char = ''
    char_count = 0

    for char in s:
        if char in "aeiou":
            if char != previous_char:
                if previous_char != '':
                    counts[previous_char] = max(counts[previous_char], char_count)
                normalized.append(char)
                char_count = 1
            else:
                char_count += 1
        previous_char = char

    if previous_char in "aeiou":
        counts[previous_char] = max(counts[previous_char], char_count)

    return ''.join(normalized), counts

def longestVowelSubsequence(s):
    normalized, counts = normalize_string(s)
    
    dp = [0] * 5  # dp数组：记录以每个元音结尾的最长有效子序列长度
                  # 索引对应关系：0→a，1→e，2→i，3→o，4→u

    for char in normalized:
        if char == 'a':
            dp[0] += counts[char]
        elif char == 'e' and dp[0] > 0:
            dp[1] = max(dp[1], dp[0] + counts[char])
        elif char == 'i' and dp[1] > 0:
            dp[2] = max(dp[2], dp[1] + counts[char])
        elif char == 'o' and dp[2] > 0:
            dp[3] = max(dp[3], dp[2] + counts[char])
        elif char == 'u' and dp[3] > 0:
            dp[4] = max(dp[4], dp[3] + counts[char])

    return dp[4]

# 示例测试用例
print(longestVowelSubsequence("aeiaaioaaaaeiiiiouuuooaauuaeiu"))  # 预期输出：13
print(longestVowelSubsequence("aeiooou"))  # 预期输出：7
print(longestVowelSubsequence("aaeeiioouu"))  # 预期输出：10
print(longestVowelSubsequence("aeiaaiooaauua"))  # 预期输出：0

内容的提问来源于stack exchange，提问作者Vokekov