A string is considered beautiful if it satisfies the following conditions:
'a', 'e', 'i', 'o', 'u') must appear at least once in it.'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 * 10^5word consists of characters 'a', 'e', 'i', 'o', and 'u'.
The description was taken from https://leetcode.com/problems/longest-substring-of-all-vowels-in-order/.
#O(N) Time, O(1) Space
class Solution:
def longestBeautifulSubstring(self, word: str) -> int:
next_vowel = {"a":"e", "e":"i", "i":"o", "o":"u", "u":""}
window = {word[0]:1}
left, right = 0, 1
longest = 0 while right < len(word):
if word[right] in window:
window[word[right]] += 1
else:
window[word[right]] = 1
if (not word[right - 1] == word[right] and
not next_vowel[word[right-1]] == word[right]):
while len(window) > 1:
window[word[left]] -= 1
if window[word[left]] == 0:
del window[word[left]]
left += 1
if len(window) == 5:
longest = max(longest, right - left + 1)
right += 1 return longestIf we're looking for the longest contiguous substring that follows a specific constraint, that is an indication that a sliding window can be applied.
We're going to have to make one major change to a traditional sliding window algorithm though.
In a traditional sliding window algorithm, once a new value is introduced to the window which is the substring that we are considering, and that value now breaks the conditions where the window would be valid, then we'd have to continuously shrink the left side of the window to make it valid again.
Here, once we hit an out-of-order vowel, we'll have to delete the entire previous window because that new vowel would not be in order with the entire previous set of vowels that we were considering.
Other than that, the rest of the process will be mostly the same. We'll create a mapping of each vowel's next vowel and we'll continue expanding our window using two pointers until we hit an out-of-order vowel. At that point, we'll remove each previous vowel of our window so we can begin fresh with a new window beginning with the new value that was just introduced. If we ever find that we have five unique vowels in our window, then we will test that window as the longest one.
Let's start by creating a mapping of each vowel with its next one.
next_vowel = {"a":"e", "e":"i", "i":"o", "o":"u", "u":""}
We'll also use a HashMap to create a mapping to keep track of each vowel we have in our window.
We'll initialize it with the first one from the input string, with an initial frequency of one.
window = {word[0]:1}
Next, we'll create two pointers, a left and a right one.
To check if a window is valid, we will continuously be checking the vowel at the right pointer with the vowel before it. That means we'll initialize our right pointer at the second index. That is also why we initialized our window HashMap with the first value of the string so that we have a previous vowel to compare when we start.
left, right = 0, 1
Lastly, we'll need an output variable which will be the longest substring that satisfies the given requirement.
longest = 0
While the right pointer hasn't passed the end of the input string, we'll continue our search.
while right < len(word):
We'll start each iteration by placing the vowel at the right pointer into the window, or incrementing its frequency if it is already there.
if word[right] in window:
window[word[right]] += 1
else:
window[word[right]] = 1
Now we'll need to check if the vowel at the right pointer is in order with the previous one we had placed.
If the current vowel and the previous one aren't the same, and the current one isn't the previous one's next vowel, then we'll need to shrink the entire window with the exception of the current vowel.
if (not word[right - 1] == word[right] and
not next_vowel[word[right-1]] == word[right]):
To do this, we will continuously remove the left vowel from the window by decrementing its frequency within the window while also incrementing the left pointer. However, if that frequency becomes zero then we'll need to delete the key from our window because it will affect the length of the window which we will be checking later.
One thing to note here is we could save ourselves a bit of time if we just deleted and remade the window, added the current right vowel, and moved the left pointer to the right index. It wouldn't change the overall time complexity of our solution, but it would stop us from revisiting each vowel twice.
Let's just keep our approach consistent with traditional sliding window algorithms though.
while len(window) > 1:
window[word[left]] -= 1
if window[word[left]] == 0:
del window[word[left]]
left += 1
Now that we have ensured our window is valid, we'll check if we have five unique values within our window.
If we do, we'll test it for the longest.
if len(window) == 5:
longest = max(longest, right - left + 1)
After we have done all of that, we will expand our window.
right += 1
Once we have considered each window, we will return the longest one we encountered.
return longest