1839. Longest Substring Of All Vowels in Order
Problem Description
A string is considered to be beautiful if it adheres to two key conditions:
- All five of the English vowels (
'a'
,'e'
,'i'
,'o'
,'u'
) must be present at least once within the string. - The characters in the string must be sorted in alphabetical order. This means all occurrences of
'a'
come before any'e'
, and so on with the remaining vowels, ordered asaeiou
.
Some examples to illustrate:
- The string
"aeiou"
qualifies as beautiful because it contains all five vowels in the correct order. "aaaaaaeiiiioou"
is also beautiful as it also respects the vowel presence and order, despite repetitions.- However, strings like
"uaeio"
,"aeoiu"
, or"aaaeeeooo"
do not meet the criteria and are not considered beautiful, either due to incorrect order or absence of certain vowels.
The task is to determine the length of the longest beautiful substring in a given string word
, which is composed solely of English vowels. A substring is a consecutive sequence of characters taken from the string. If no beautiful substring exists, the answer should be 0
.
Intuition
To find the solution to this problem, we take a step-by-step approach by breaking down the string into distinguishable parts according to the character transitions. Our goal is to identify consecutive groups of the same vowel and note down their position and length. This way, we can later check if these groups form a valid sequence that matches our conditions for a beautiful string.
Here's how we can conceptualize our approach:
-
Traverse the given string while keeping track of sequences of identical characters. For instance, in the string
"aaeeiioouu"
, we'd identify the sequences as['aa', 'ee', 'ii', 'oo', 'uu']
. -
Store information about these sequences in a way that we can later check the sequence order. In the implementation, this is done by storing pairs of the character and its sequence length in an array.
-
With this array of vowel sequences, we can now look for subsequences of five elements where each character is exactly one of the vowels in the correct order
'a'
,'e'
,'i'
,'o'
,'u'
. When we find such a sequence, we calculate its total length by summing the lengths of its constituents. -
As we may have several eligible beautiful subsequences, we want to find the longest one. Therefore, we iterate through all possible subsequences that could be beautiful and retain the maximum length found.
By simplifying the problem to identifying and evaluating sequences of vowels, and checking for the longest valid sequence, we can effectively solve the problem in a straightforward and efficient manner.
Learn more about Sliding Window patterns.
Solution Approach
The implemented solution follows these steps:
-
Initialize a list to store character sequence information: The list
arr
is used to store tuples of characters and their sequence lengths. It starts empty and is populated as we iterate through the input string. -
Loop through the string to fill the sequence list: The outer
while
loop keeps track of our positioni
in the stringword
. For each positioni
, an innerwhile
loop counts the length of the sequence of the same character starting from that position. The character and its sequence length are then appended as a tuple to thearr
list. The value ofi
is updated to the position following the end of the current sequence. -
Initialize a variable to keep track of the answer:
ans
is initialized to 0 and is used to record the length of the longest beautiful substring. It will be updated throughout the algorithm whenever a longer beautiful substring is found. -
Search for beautiful substrings: A
for
loop iterates through thearr
list, checking combinations of 5 consecutive character sequences. It extracts these five sequences using slicing (a, b, c, d, e = arr[i : i + 5]
) and checks if the characters form the sequence'aeiou'
. -
Update the maximum length if a beautiful substring is found: If the sequence of characters is correct, it computes the length of this beautiful substring by summing the lengths of its sequence (
a[1] + b[1] + c[1] + d[1] + e[1]
) and updatesans
if this length is greater than the currentans
. -
Return the result: After iterating through all possible substrings, the algorithm returns the maximum length found (
ans
), which represents the length of the longest beautiful substring.
Here are the key algorithms, data structures, and patterns used:
-
Data Structure (List of Tuples): The list
arr
of tuples is crucial for keeping track of sequences of the same character and their lengths. This allows for efficient access and analysis of contiguous segments that may form parts of a beautiful substring. -
Two-Pointer Technique: The algorithm uses two pointers (
i
andj
) to identify the sequences of identical characters. The first pointeri
marks the start of a sequence, while the second pointerj
moves ahead to find the end of that sequence. -
Sliding Window: By checking slices of 5 consecutive elements in
arr
, the algorithm effectively uses a sliding window of size 5 to identify potential beautiful substrings. -
Greedy Approach: By always updating
ans
with the maximum length found, we ensure that by the end of the algorithm, we have greedily found the longest beautiful substring.
Taken together, this approach efficiently identifies the longest beautiful substring by combining sequence aggregation and step-by-step analysis with a logical check for the "beautiful" conditions.
Ready to land your dream job?
Unlock your dream job with a 2-minute evaluator for a personalized learning plan!
Start EvaluatorExample Walkthrough
Let's take a small example string "aeeiouuiaeiou"
to illustrate the solution approach described above. We'll walk through each step of the solution using this string.
-
Initialize a list to store character sequence information: We start with an empty list
arr
. -
Loop through the string to fill the sequence list: We would start at the first character
a
and notice that the next character ise
, so we have a sequence of"a"
with a length of1
. We add(a, 1)
to ourarr
list.Continuing this process, we would get the following sequences:
- Sequence of
"e"
with length2
, so we add(e, 2)
to ourarr
. - Sequence of
"i"
with length1
, so we add(i, 1)
to ourarr
. - Sequence of
"ou"
with length3
, sinceo
andu
are different, we add(o, 2)
for the twoo
s and then(u, 1)
for the singleu
. - This process repeats until the end of the string, resulting in our
arr
being[(a, 1), (e, 2), (i, 1), (o, 2), (u, 1), (i, 1), (a, 1), (e, 1), (i, 1), (o, 1), (u, 1)]
.
- Sequence of
-
Initialize a variable to keep track of the answer: We set
ans = 0
as we have not found any beautiful substrings yet. -
Search for beautiful substrings: We start iterating over
arr
to find sequences of five consecutive character sequences that match'aeiou'
. -
Update the maximum length if a beautiful substring is found: As we iterate, we check slices of
arr
such asarr[0:5]
which would give us[(a, 1), (e, 2), (i, 1), (o, 2), (u, 1)]
. This is a beautiful sequence because the characters are in the correct'aeiou'
order. We, therefore, calculate the length of this beautiful substring as1 + 2 + 1 + 2 + 1 = 7
and updateans
to7
because it is greater than the currentans
.When we reach the slice
arr[5:10]
, which is[(i, 1), (a, 1), (e, 1), (i, 1), (o, 1)]
, we do not have a beautiful sequence since the characters are not in the correct order. -
Return the result: After iterating through the entire list
arr
, the algorithm finds that the longest beautiful substring length is7
, and that is what it returns.
Therefore, for the example string "aeeiouuiaeiou"
, the algorithm would correctly identify the longest beautiful substring "aeeiouu"
and return its length, 7
.
Solution Implementation
1class Solution:
2 def longestBeautifulSubstring(self, word: str) -> int:
3 # Initialize a list to store tuples of characters and their consecutive counts
4 consecutive_chars = []
5 length_of_word = len(word)
6 index = 0
7
8 # Iterate through the word to group consecutive characters together
9 while index < length_of_word:
10 # Start of a new character sequence
11 start_index = index
12 # Move index forward while the characters are the same
13 while index < length_of_word and word[index] == word[start_index]:
14 index += 1
15 # Append the character and its consecutive count to the list
16 consecutive_chars.append((word[start_index], index - start_index))
17
18 # Set initial answer to 0
19 max_length = 0
20
21 # Iterate through the grouped character list to find beautiful substrings
22 for i in range(len(consecutive_chars) - 4): # We need at least 5 different vowels
23 # Unpack the next five elements in the list
24 char_seq1, char_seq2, char_seq3, char_seq4, char_seq5 = consecutive_chars[i: i + 5]
25 # Check if current sequence forms "aeiou"
26 if char_seq1[0] + char_seq2[0] + char_seq3[0] + char_seq4[0] + char_seq5[0] == "aeiou":
27 # Calculate the total length of the current beautiful substring
28 current_length = char_seq1[1] + char_seq2[1] + char_seq3[1] + char_seq4[1] + char_seq5[1]
29 # Update the answer if we found a longer beautiful substring
30 max_length = max(max_length, current_length)
31
32 # Return the length of the longest beautiful substring found
33 return max_length
34
1class Solution {
2
3 // Method to find the length of the longest beautiful substring in the input string
4 public int longestBeautifulSubstring(String word) {
5 int wordLength = word.length(); // Store the length of the word
6 List<CharGroup> charGroups = new ArrayList<>(); // List to store groups of consecutive identical characters
7
8 // Loop through the string and group consecutive identical characters
9 for (int i = 0; i < wordLength;) {
10 int j = i;
11 // Find the end index of the group of identical characters
12 while (j < wordLength && word.charAt(j) == word.charAt(i)) {
13 ++j;
14 }
15 // Add the group to the list
16 charGroups.add(new CharGroup(word.charAt(i), j - i));
17 i = j; // Move to the next group
18 }
19
20 int maxBeautyLength = 0; // Variable to track the maximum length of a beautiful substring
21
22 // Iterate through the list of char groups to find the longest beautiful substring
23 for (int i = 0; i < charGroups.size() - 4; ++i) {
24 // Get five consecutive char groups
25 CharGroup a = charGroups.get(i),
26 b = charGroups.get(i + 1),
27 c = charGroups.get(i + 2),
28 d = charGroups.get(i + 3),
29 e = charGroups.get(i + 4);
30
31 // Check if the groups form a sequence 'a', 'e', 'i', 'o', 'u'
32 if (a.character == 'a' && b.character == 'e' && c.character == 'i'
33 && d.character == 'o' && e.character == 'u') {
34 // Calculate the total length of the beautiful substring and update the max length
35 maxBeautyLength = Math.max(maxBeautyLength, a.count + b.count + c.count + d.count + e.count);
36 }
37 }
38
39 return maxBeautyLength; // Return the maximum length found
40 }
41}
42
43// Helper class to represent a group of consecutive identical characters
44class CharGroup {
45 char character; // The character in the group
46 int count; // The count of how many times the character is repeated
47
48 // Constructor for the helper class
49 CharGroup(char character, int count) {
50 this.character = character;
51 this.count = count;
52 }
53}
54
1class Solution {
2public:
3 int longestBeautifulSubstring(string word) {
4 // Vector to store pairs of characters and their consecutive frequencies.
5 vector<pair<char, int>> charFrequencies;
6 int length = word.size();
7
8 // Convert the word into pairs of characters and their consecutive counts.
9 for (int i = 0; i < length;) {
10 int j = i;
11 while (j < length && word[j] == word[i]) {
12 ++j;
13 }
14 charFrequencies.push_back({word[i], j - i});
15 i = j; // Move to the next unique character.
16 }
17
18 int maxBeautyLength = 0; // To store the length of the longest beautiful substring
19
20 // Loop through the charFrequencies array to find all possible beautiful substrings.
21 for (int i = 0; i < static_cast<int>(charFrequencies.size()) - 4; ++i) {
22 auto& [currentChar, currentFreq] = charFrequencies[i];
23 auto& [nextChar1, freq1] = charFrequencies[i + 1];
24 auto& [nextChar2, freq2] = charFrequencies[i + 2];
25 auto& [nextChar3, freq3] = charFrequencies[i + 3];
26 auto& [nextChar4, freq4] = charFrequencies[i + 4];
27
28 // Check if we have a sequence 'aeiou', denoting a beautiful substring.
29 if (currentChar == 'a' && nextChar1 == 'e' && nextChar2 == 'i' &&
30 nextChar3 == 'o' && nextChar4 == 'u') {
31 // Calculate the length of the beautiful substring and update maxBeautyLength.
32 int beautyLength = currentFreq + freq1 + freq2 + freq3 + freq4;
33 maxBeautyLength = max(maxBeautyLength, beautyLength);
34 }
35 }
36
37 // Return the length of the longest beautiful substring found.
38 return maxBeautyLength;
39 }
40};
41
1function longestBeautifulSubstring(word: string): number {
2 // Array to store pairs of characters and their consecutive frequencies.
3 const charFrequencies: { character: string; frequency: number }[] = [];
4 const length: number = word.length;
5
6 // Convert the word into objects with characters and their consecutive counts.
7 for (let i = 0; i < length;) {
8 let j = i;
9 while (j < length && word[j] === word[i]) {
10 ++j;
11 }
12 charFrequencies.push({ character: word[i], frequency: j - i });
13 i = j; // Move to the next unique character.
14 }
15
16 let maxBeautyLength: number = 0; // To store the length of the longest beautiful substring
17
18 // Iterate through the charFrequencies array to find all possible beautiful substrings.
19 for (let i = 0; i < charFrequencies.length - 4; ++i) {
20 const currentChar = charFrequencies[i].character;
21 const currentFreq = charFrequencies[i].frequency;
22 const nextChar1 = charFrequencies[i + 1].character;
23 const freq1 = charFrequencies[i + 1].frequency;
24 const nextChar2 = charFrequencies[i + 2].character;
25 const freq2 = charFrequencies[i + 2].frequency;
26 const nextChar3 = charFrequencies[i + 3].character;
27 const freq3 = charFrequencies[i + 3].frequency;
28 const nextChar4 = charFrequencies[i + 4].character;
29 const freq4 = charFrequencies[i + 4].frequency;
30
31 // Check if we have a sequence 'aeiou', denoting a beautiful substring.
32 if (currentChar === 'a' && nextChar1 === 'e' && nextChar2 === 'i' &&
33 nextChar3 === 'o' && nextChar4 === 'u') {
34 // Calculate the length of the beautiful substring and update maxBeautyLength.
35 const beautyLength = currentFreq + freq1 + freq2 + freq3 + freq4;
36 maxBeautyLength = Math.max(maxBeautyLength, beautyLength);
37 }
38 }
39
40 // Return the length of the longest beautiful substring found.
41 return maxBeautyLength;
42}
43
Time and Space Complexity
Time Complexity
The time complexity of the given code can be analyzed in the following steps:
-
Constructing the
arr
list: This involves a single pass through the input stringword
with a pair of pointersi
andj
. For each unique character in the word, the loop checks for consecutive occurrences and adds a tuple(character, count)
toarr
. This operation has a time complexity ofO(n)
wheren
is the length of the input string since each character is considered exactly once. -
Looping through
arr
for finding the longest beautiful substring: The second loop runs with an upper limit oflen(arr) - 4
, and for each iteration, it checks a fixed sequence of 5 elements (not considering nested loops). The check andmax
call areO(1)
operations. The number of iterations depends on the number of unique characters inword
, but since it's strictly less thann
, the loop has a time complexity ofO(n)
.
Combining both parts, the overall time complexity is O(n) + O(n) = O(n)
.
Space Complexity
The space complexity is determined by additional space used apart from the input:
-
The
arr
list: In the worst case, if every character inword
is unique,arr
would haven
tuples. Therefore, the space complexity due toarr
isO(n)
. -
Constant space for variables
i
,j
, andans
, which doesn't depend on the size of the input.
Hence, the overall space complexity of the code is O(n)
.
Learn more about how to find time and space complexity quickly using problem constraints.
How many times is a tree node visited in a depth first search?
Recommended Readings
https algomonster s3 us east 2 amazonaws com cover_photos stack svg Sliding Window Maximum Monotonic Stack We have an array and a sliding window defined by a start index and an end index The sliding window moves from left of the array to right There are always k elements in
LeetCode Patterns Your Personal Dijkstra's Algorithm to Landing Your Dream Job The goal of AlgoMonster is to help you get a job in the shortest amount of time possible in a data driven way We compiled datasets of tech interview problems and broke them down by patterns This way we
Recursion Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https algomonster s3 us east 2 amazonaws com recursion jpg You first
Want a Structured Path to Master System Design Too? Donāt Miss This!