Как найти самую длинную подпоследовательность, содержащую все гласные по порядку в строке в Python? ⇐ Python

[Anonymous]

Я работаю над проблемой, где мне нужно найти длину самой длинной подпоследовательности в заданной строке, содержащей все гласные (a, e, i, o, u) по порядку и никаких гласных не по порядку. Гласные могут повторяться, но они должны быть в правильном порядке.
Например:

• Строка aeiaaioaaaaeiiiiouuuooaauuaeiu< /code> должен возвращать 13, поскольку самая длинная допустимая подпоследовательность — это aaaaeiiiiouuu, длина которой равна 13.
• Строка aeiooou должна возвращать 7, поскольку самой длинной допустимой подпоследовательностью является aeiooou, длина которой равна 7.
• Строка aaeeiioouu должна возвращать 10 потому что самая длинная допустимая подпоследовательность — это 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 array to keep track of the longest subsequence ending at each vowel

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]

# Example tests
print(longestVowelSubsequence("aeiaaioaaaaeiiiiouuuooaauuaeiu")) # Should return 13
print(longestVowelSubsequence("aeiooou")) # Should return 7
print(longestVowelSubsequence("aaeeiioouu")) # Should return 10
print(longestVowelSubsequence("aeiaaiooaauua")) # Should return 0


Подробнее здесь: https://stackoverflow.com/questions/786 ... a-string-i