Leetcode 1839: Longest Substring Of All Vowels in Order
A string is considered beautiful if it satisfies the following conditions: each of the five vowels (‘a’, ’e’, ‘i’, ‘o’, ‘u’) must appear at least once, and the characters must appear in alphabetical order. 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.
Problem
Approach
Steps
Complexity
Input: The input consists of a string word containing only vowels ('a', 'e', 'i', 'o', 'u').
Example: word = 'aeiouaeiouaei'
Constraints:
• 1 <= word.length <= 5 * 10^5
• word consists only of characters 'a', 'e', 'i', 'o', 'u'.
Output: The output is an integer representing the length of the longest beautiful substring in the word.
Example: 11
Constraints:
Goal: To find the longest contiguous substring that contains all five vowels at least once and appears in alphabetical order.
Steps:
• Initialize a map for vowel indices.
• Iterate through the string and use a sliding window to track the longest valid substring that meets the conditions of a beautiful string.
• Update the result with the longest valid substring found during iteration.
Goal: The problem ensures that the input will contain only vowels and that the length of the input will be manageable.
Steps:
• 1 <= word.length <= 5 * 10^5
• word consists only of characters 'a', 'e', 'i', 'o', 'u'.
Assumptions:
• The input string will always contain characters from the set { 'a', 'e', 'i', 'o', 'u' }.
• The string will have at least 1 character.
• Input: word = 'aeiouaeiouaei'
• Explanation: The longest beautiful substring in 'aeiouaeiouaei' is 'aeiouaeioua' because it contains all vowels in the correct order and is the longest such substring.
Approach: To solve this problem, we can use a sliding window approach to iterate through the string and keep track of the longest valid substring. The window is valid if it contains all five vowels and they appear in order.
Observations:
• We need to track the positions of each vowel in the string to check if they appear in the correct order.
• A sliding window is a natural choice here since we are looking for a contiguous sequence of characters.
Steps:
• Initialize a map to store the indices of the vowels 'a', 'e', 'i', 'o', 'u'.
• Iterate through the string and use a sliding window to check for the longest valid substring.
• Track the start and end positions of the window and update the result whenever a valid substring is found.
Empty Inputs:
• The input string will always contain at least one character, so this case does not need to be handled explicitly.
Large Inputs:
• The solution should be efficient enough to handle large strings up to 5 * 10^5 characters.
Special Values:
• Strings with only one type of vowel or without all five vowels cannot be considered beautiful.
Constraints:
• The solution must work for strings of varying lengths, from 1 to 5 * 10^5 characters.
int longestBeautifulSubstring(string s) {
map<char, int> idx;
idx['a'] = 0;
idx['e'] = 1;
idx['i'] = 2;
idx['o'] = 3;
idx['u'] = 4;
int j = 0, res = 0, n = s.size();
int id = -1;
for(int i = 0; i < n; i++) {
if(s[i] == 'a') {
if(id != 0) {
j = i;
}
id = 0;
}else if((idx[s[i]] < id) || (idx[s[i]] - id > 1)) {
id = -1;
j = i;
} else if(idx[s[i]] - id == 1) {
id = idx[s[i]];
}
if(id == 4) {
res = max(res, i - j + 1);
}
}
return res;
}
1 : Function Definition
int longestBeautifulSubstring(string s) {
Defines the function `longestBeautifulSubstring`, which takes a string `s` and returns the length of the longest substring containing the vowels 'a', 'e', 'i', 'o', 'u' in order.
2 : Map Initialization
map<char, int> idx;
Declares a map `idx` that associates each vowel with a corresponding integer value to track the order in which the vowels should appear.
3 : Assign Vowel Indexes
idx['a'] = 0;
Assigns 0 to 'a' in the map `idx`, representing its position in the sequence of vowels.
4 : Assign Vowel Indexes
idx['e'] = 1;
Assigns 1 to 'e' in the map `idx`, representing its position in the sequence of vowels.
5 : Assign Vowel Indexes
idx['i'] = 2;
Assigns 2 to 'i' in the map `idx`, representing its position in the sequence of vowels.
6 : Assign Vowel Indexes
idx['o'] = 3;
Assigns 3 to 'o' in the map `idx`, representing its position in the sequence of vowels.
7 : Assign Vowel Indexes
idx['u'] = 4;
Assigns 4 to 'u' in the map `idx`, representing its position in the sequence of vowels.
8 : Variable Initialization
int j = 0, res = 0, n = s.size();
Initializes variables: `j` to track the starting index of the current substring, `res` to store the result (longest valid substring length), and `n` for the size of the input string `s`.
9 : Variable Initialization
int id = -1;
Initializes the variable `id` to -1 to keep track of the most recent vowel index in the substring.
10 : For Loop
for(int i = 0; i < n; i++) {
Starts a loop to iterate through the string `s` character by character.
11 : Check for 'a'
if(s[i] == 'a') {
Checks if the current character is 'a'.
12 : Check and Update Window
if(id != 0) {
If the previous vowel was not 'a', reset the start of the window by setting `j` to the current index `i`.
13 : Update Start Index
j = i;
Sets `j` to the current index `i` to start a new potential substring.
14 : Update Vowel Index
id = 0;
Sets the vowel index `id` to 0, representing the 'a' vowel.
15 : Check for Invalid Vowel Sequence
}else if((idx[s[i]] < id) || (idx[s[i]] - id > 1)) {
Checks if the current character does not follow the correct vowel sequence or if it's out of order.
16 : Reset Vowel Sequence
id = -1;
Resets `id` to -1 and `j` to the current index `i`, marking the start of a new potential valid substring.
17 : Update Start Index
j = i;
Resets the starting index `j` because the current character breaks the valid vowel order.
18 : Check for Valid Vowel Progression
} else if(idx[s[i]] - id == 1) {
Checks if the current character is the next vowel in the sequence.
19 : Update Vowel Index
id = idx[s[i]];
Updates the vowel index `id` to the index of the current character.
20 : Check for Full Sequence
if(id == 4) {
Checks if the substring has reached the end of the vowel sequence, 'u'.
21 : Update Result
res = max(res, i - j + 1);
Updates the result `res` with the length of the current valid substring if it's longer than the previous longest substring.
22 : Return Result
return res;
Returns the length of the longest beautiful substring found.
Best Case: O(n)
Average Case: O(n)
Worst Case: O(n)
Description: The time complexity is O(n) because we only need to iterate over the string once.
Best Case: O(1)
Worst Case: O(1)
Description: The space complexity is O(1) as we only need a constant amount of extra space for the sliding window.
| LeetCode Solutions Library / DSA Sheets / Course Catalog |
|---|
comments powered by Disqus