1839. Longest Substring Of All Vowels in Order
Description
A string is considered beautiful if it satisfies the following conditions:
- Each of the 5 English vowels (
'a'
,'e'
,'i'
,'o'
,'u'
) must appear at least once in it. - The letters must be sorted in alphabetical order (i.e. all
'a'
s before'e'
s, all'e'
s before'i'
s, etc.).
For example, strings "aeiou"
and "aaaaaaeiiiioou"
are considered beautiful, but "uaeio"
, "aeoiu"
, and "aaaeeeooo"
are not beautiful.
Given a string word
consisting of English vowels, return the length of the longest beautiful substring of word
. If no such substring exists, return 0
.
A substring is a contiguous sequence of characters in a string.
Example 1:
Input: word = "aeiaaioaaaaeiiiiouuuooaauuaeiu" Output: 13 Explanation: The longest beautiful substring in word is "aaaaeiiiiouuu" of length 13.
Example 2:
Input: word = "aeeeiiiioooauuuaeiou" Output: 5 Explanation: The longest beautiful substring in word is "aeiou" of length 5.
Example 3:
Input: word = "a" Output: 0 Explanation: There is no beautiful substring, so return 0.
Constraints:
1 <= word.length <= 5 * 105
word
consists of characters'a'
,'e'
,'i'
,'o'
, and'u'
.
Solutions
Solution 1: Two Pointers + Simulation
We can first transform the string word
. For example, for word="aaaeiouu"
, we can transform it into data items ('a', 3)
, ('e', 1)
, ('i', 1)
, ('o', 1)
, ('u', 2)
and store them in an array arr
. Each data item's first element represents a vowel, and the second element represents the number of times the vowel appears consecutively. This transformation can be implemented using two pointers.
Next, we traverse the array arr
, each time taking $5$ adjacent data items, and judge whether the vowels in these data items are 'a'
, 'e'
, 'i'
, 'o'
, 'u'
respectively. If so, calculate the total number of times the vowels appear in these $5$ data items, which is the length of the current beautiful substring, and update the maximum value of the answer.
The time complexity is $O(n)$, and the space complexity is $O(n)$. Where $n$ is the length of the string word
.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 |
|