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'
.
Solution: Counter
Use a counter to track how many unique vowels we saw so far. Reset the counter whenever the s[i] < s[i-1]. Incase the counter if s[i] > s[i – 1]. When counter becomes 5, we know we found a valid substring.
Time complexity: O(n)
Space complexity: O(1)
C++
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 |
// Author: Huahua class Solution { public: int longestBeautifulSubstring(string word) { const int n = word.length(); int ans = 0; char p = 'a' - 1; for (int i = 0, vowels = 0, l = 0; i < n; ++i) { if (word[i] < p) { vowels = (word[i] == 'a'); l = i; } else if (word[i] > p) { ++vowels; } if (vowels == 5) ans = max(ans, i - l + 1); p = word[i]; } return ans; } }; |
请尊重作者的劳动成果,转载请注明出处!花花保留对文章/视频的所有权利。
如果您喜欢这篇文章/视频,欢迎您捐赠花花。
If you like my articles / videos, donations are welcome.
Be First to Comment