Longest Ordered Subsequence of Vowels

Problem Given a string of only vowels, find the length of the longest subsequence consisting of all five vowels in order: one or more 'a's, then 'e's, then 'i's, then 'o's, then 'u's.

Input / Output

• Input: string s of characters {a,e,i,o,u}.
• Output: length of the longest valid subsequence (0 if none uses all five).

Constraints

• |s| up to 10^5 — O(n * 5) DP expected; naive memoization on (index, lastChar) without compaction can TLE.

Example

• s = "aeiaaioooaauuaeiou" → 10 (pick six a's, then e, i, o, u in order).

Expected approach

• DP over the 5 vowel stages: dp[v] = best length of a valid subsequence ending at vowel stage v. For each char c at stage v: dp[v] = max(dp[v], dp[v-1]) + 1 (extend same stage or transition from previous stage; dp[v-1] must be non-empty). Answer = dp[u] if all stages were filled. O(n) time, O(1) space.