1839. Longest Substring Of All Vowels in Order

MediumStringSliding Window
Leetcode Link

Problem Description

A string is considered to be beautiful if it adheres to two key conditions:

  1. All five of the English vowels ('a', 'e', 'i', 'o', 'u') must be present at least once within the string.
  2. 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 as aeiou.

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:

  1. 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'].

  2. 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.

  3. 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.

  4. 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.

Not Sure What to Study? Take the 2-min Quiz to Find Your Missing Piece：

Which algorithm should you use to find a node that is close to the root of the tree?

Solution Approach

The implemented solution follows these steps:

  1. 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.

  2. Loop through the string to fill the sequence list: The outer while loop keeps track of our position i in the string word. For each position i, an inner while 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 the arr list. The value of i is updated to the position following the end of the current sequence.

  3. 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.

  4. Search for beautiful substrings: A for loop iterates through the arr 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'.

  5. 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 updates ans if this length is greater than the current ans.

  6. 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 and j) to identify the sequences of identical characters. The first pointer i marks the start of a sequence, while the second pointer j 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.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

Consider the classic dynamic programming of fibonacci numbers, what is the recurrence relation?

Example 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.

  1. Initialize a list to store character sequence information: We start with an empty list arr.

  2. Loop through the string to fill the sequence list: We would start at the first character a and notice that the next character is e, so we have a sequence of "a" with a length of 1. We add (a, 1) to our arr list.

    Continuing this process, we would get the following sequences:

    • Sequence of "e" with length 2, so we add (e, 2) to our arr.
    • Sequence of "i" with length 1, so we add (i, 1) to our arr.
    • Sequence of "ou" with length 3, since o and u are different, we add (o, 2) for the two os and then (u, 1) for the single u.
    • 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)].

  3. Initialize a variable to keep track of the answer: We set ans = 0 as we have not found any beautiful substrings yet.

  4. Search for beautiful substrings: We start iterating over arr to find sequences of five consecutive character sequences that match 'aeiou'.

  5. Update the maximum length if a beautiful substring is found: As we iterate, we check slices of arr such as arr[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 as 1 + 2 + 1 + 2 + 1 = 7 and update ans to 7 because it is greater than the current ans.

    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.

  6. Return the result: After iterating through the entire list arr, the algorithm finds that the longest beautiful substring length is 7, 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
Not Sure What to Study? Take the 2-min Quiz：

What's the output of running the following function using input [30, 20, 10, 100, 33, 12]?

1def fun(arr: List[int]) -> List[int]:
2    import heapq
3    heapq.heapify(arr)
4    res = []
5    for i in range(3):
6        res.append(heapq.heappop(arr))
7    return res
8
1public static int[] fun(int[] arr) {
2    int[] res = new int[3];
3    PriorityQueue<Integer> heap = new PriorityQueue<>();
4    for (int i = 0; i < arr.length; i++) {
5        heap.add(arr[i]);
6    }
7    for (int i = 0; i < 3; i++) {
8        res[i] = heap.poll();
9    }
10    return res;
11}
12
1class HeapItem {
2    constructor(item, priority = item) {
3        this.item = item;
4        this.priority = priority;
5    }
6}
7
8class MinHeap {
9    constructor() {
10        this.heap = [];
11    }
12
13    push(node) {
14        // insert the new node at the end of the heap array
15        this.heap.push(node);
16        // find the correct position for the new node
17        this.bubble_up();
18    }
19
20    bubble_up() {
21        let index = this.heap.length - 1;
22
23        while (index > 0) {
24            const element = this.heap[index];
25            const parentIndex = Math.floor((index - 1) / 2);
26            const parent = this.heap[parentIndex];
27
28            if (parent.priority <= element.priority) break;
29            // if the parent is bigger than the child then swap the parent and child
30            this.heap[index] = parent;
31            this.heap[parentIndex] = element;
32            index = parentIndex;
33        }
34    }
35
36    pop() {
37        const min = this.heap[0];
38        this.heap[0] = this.heap[this.size() - 1];
39        this.heap.pop();
40        this.bubble_down();
41        return min;
42    }
43
44    bubble_down() {
45        let index = 0;
46        let min = index;
47        const n = this.heap.length;
48
49        while (index < n) {
50            const left = 2 * index + 1;
51            const right = left + 1;
52
53            if (left < n && this.heap[left].priority < this.heap[min].priority) {
54                min = left;
55            }
56            if (right < n && this.heap[right].priority < this.heap[min].priority) {
57                min = right;
58            }
59            if (min === index) break;
60            [this.heap[min], this.heap[index]] = [this.heap[index], this.heap[min]];
61            index = min;
62        }
63    }
64
65    peek() {
66        return this.heap[0];
67    }
68
69    size() {
70        return this.heap.length;
71    }
72}
73
74function fun(arr) {
75    const heap = new MinHeap();
76    for (const x of arr) {
77        heap.push(new HeapItem(x));
78    }
79    const res = [];
80    for (let i = 0; i < 3; i++) {
81        res.push(heap.pop().item);
82    }
83    return res;
84}
85

Time and Space Complexity

Time Complexity

The time complexity of the given code can be analyzed in the following steps:

  1. Constructing the arr list: This involves a single pass through the input string word with a pair of pointers i and j. For each unique character in the word, the loop checks for consecutive occurrences and adds a tuple (character, count) to arr. This operation has a time complexity of O(n) where n is the length of the input string since each character is considered exactly once.

  2. Looping through arr for finding the longest beautiful substring: The second loop runs with an upper limit of len(arr) - 4, and for each iteration, it checks a fixed sequence of 5 elements (not considering nested loops). The check and max call are O(1) operations. The number of iterations depends on the number of unique characters in word, but since it's strictly less than n, the loop has a time complexity of O(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:

  1. The arr list: In the worst case, if every character in word is unique, arr would have n tuples. Therefore, the space complexity due to arr is O(n).

  2. Constant space for variables i, j, and ans, 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.

Fast Track Your Learning with Our Quick Skills Quiz:

Given an array of 1,000,000 integers that is almost sorted, except for 2 pairs of integers. Which algorithm is fastest for sorting the array?

Recommended Readings

Sliding Window Maximum

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 - Top Patterns for Coding Interviews

Top Patterns to Conquer the Technical Coding Interview Should the written word bore you fear not A delightful video alternative awaits iframe width 560 height 315 src https www youtube com embed LW8Io6IPYHw title YouTube video player frameborder 0 allow accelerometer autoplay clipboard write encrypted media gyroscope picture in picture

Recursion Review

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

Got a question? Ask the Teaching Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.

←
↑TA 👨‍🏫