1371. Find the Longest Substring Containing Vowels in Even Counts

MediumBit ManipulationHash TableStringPrefix Sum
Leetcode Link

Problem Description

In this problem, you're given a string s. Your task is to find the length of the longest substring of s where each of the vowels - 'a', 'e', 'i', 'o', 'u' - appears an even number of times. Substrings are continuous parts of the original string, and in this case, any substring that satisfies the vowel condition could potentially be the longest. The goal is to figure out the maximum length possible while adhering to the even occurrence condition for vowels.

Intuition

The intuition behind the solution is to use a bitwise representation to track the count of vowels in the substring efficiently. Because we only care about even or odd occurrences, we don't need to keep a count of each vowel; we only need to know if a vowel has appeared an even or odd number of times. Thus, each vowel can be represented with 1 bit, resulting in a 5-bit integer for all five vowels (where 0 means even and 1 means odd number of occurrences).

The key insight is that if at two different points in the string, the 5-bit integer (or state) is the same, it means that we have a substring (between these two points) where all vowels have appeared an even number of times.

The solution iterates through the string and toggles the respective bit in the state when a vowel is found. If the state has been seen before, we calculate the length of the new substring ending at the current character and update the answer if it's longer than the previous maximum. The pos array keeps track of the first occurrence of each state to calculate lengths of valid substrings. We start by initializing the pos array with inf to denote that those states have not been seen yet, except for the state 0, which is initialized to -1 to handle the edge case where a valid substring starts at the beginning of the input string.

By using this bitwise state and the pos array, we can efficiently find the longest substring where all vowels appear an even number of times.

Learn more about Prefix Sum patterns.

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

A person thinks of a number between 1 and 1000. You may ask any number questions to them, provided that the question can be answered with either "yes" or "no".

What is the minimum number of questions you needed to ask so that you are guaranteed to know the number that the person is thinking?

Solution Approach

The solution utilizes a bitwise approach combined with a hash map (implemented as a list called pos in the code) to keep track of the indices at which each state occurs for the first time.

Key Components of the Solution:

  • Vowels Bitmasking: Each vowel has a corresponding bit in a 5-bit integer, where the order is 'a', 'e', 'i', 'o', 'u'. For example, if only 'a' and 'i' have been seen an odd number of times, the state would be 10100 in binary, which is 20 in decimal.

  • Tracking States: The state variable is a 5-bit integer representing the current state of vowels' counts (even/odd). The initial state is 0 since we start with an even count (zero occurrences) for all vowels.

  • Index Memory (pos): An array called pos of size 32 (since there are 2^5 possible states due to 5 vowels) is used to remember the earliest occurrence of every state. This array is initialized with inf, except for pos[0] which is set to -1.

  • Iterating Through the String: As we iterate through the string, we check each character. If it's a vowel, we flip the corresponding bit in the state using the exclusive OR (XOR) operation: state ^= 1 << j, where j is the index of the vowel in the string 'aeiou'.

  • Updating the Answer: With each new character processed, we check if the current state has been encountered before:

    • If it's been seen, we calculate the length of the substring from the first occurrence of this state to the current position.
    • If the calculated length is greater than the ans (which keeps track of the maximum length seen so far), we update ans.

  • First Occurrence: We also check if the current state's first occurrence needs to be updated in the pos array. If the current index is less than the stored value in pos[state], we update pos[state] with the current index.

By the end of the string traversal, ans will hold the length of the longest substring where all vowels appear an even number of times, and that's what we return as the solution.

Example Walkthrough:

Let's walk through a quick example:

1s = "eleetminicoworoep"
  • We start at state = 0 and pos[0] = -1 because we have an even count (zero) for all vowels at the start.
  • Iterating over s, whenever we encounter a vowel, we update state. Suppose state becomes 3 after some operations; this means 'a' and 'e' have been seen an odd number of times so far.
  • If state is 3 again at a later point, we know that between these two indices, 'a' and 'e' must have appeared an even number of times. Therefore, we calculate the length of this substring and check if it's the maximum.
  • We continue this process until the end of the string, constantly updating ans with longer valid substrings as we find them.

The implementation is efficient with a time complexity of O(n), where n is the length of the string, because we only need a single pass through the string to compute the result, and each operation within that pass is of constant time complexity.

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

What is the worst case running time for finding an element in a binary search tree(not necessarily balanced) of size n?

Example Walkthrough

Let's illustrate the solution approach using the string:

1s = "aeiobcdf"

  1. Initialize the pos array with length 32 to represent all possible states of vowel occurrences (2^5 for 5 vowels). Set all values to inf, except pos[0] to -1.

  2. We start with state = 0 (since no vowels have been seen yet) and ans = 0 (since no substrings have been found yet).

  3. As we iteratively check each character in s, we use the following steps:

    • When at index 0, s[0] = 'a': We see our first vowel 'a'. The bit for 'a' in the state is toggled from 0 to 1. Now, state = 00001.
    • At index 1, s[1] = 'e': We toggle the bit for 'e'. Now, state = 00011.
    • At index 2, s[2] = 'i': Toggling the 'i' bit: state = 00111.
    • At index 3, s[3] = 'o': Toggling 'o': state = 01111.
    • At index 4, s[4] = 'b': 'b' is not a vowel; state remains 01111.
    • At index 5, s[5] = 'c': 'c' is not a vowel; state remains 01111.
    • At index 6, s[6] = 'd': 'd' is not a vowel; state remains 01111.
    • At index 7, s[7] = 'f': 'f' is not a vowel; state remains 01111.

  4. We've reached the end of the string, and throughout, each vowel has appeared exactly once, so their counts are odd. Our final state is 01111.

  5. Throughout our iteration, the state has changed from 00000 to 01111. After toggling the bits whenever we encountered a vowel, we checked pos to see if the current state had been recorded before. In this instance, since no state repeated other than the initial state 0, the length of the longest valid substring is zero because we have not encountered a state twice where the state would be 00000 again (meaning that all vowels have an even count).

So, the ans remains 0 in this example; there are no substrings where each vowel occurs an even number of times.

The key takeaway is the tracking of vowel occurrences through bit manipulation, using XOR to toggle between even and odd counts, and using the pos array to store the first occurrence of a state. This approach allows for quick lookups and updates while maintaining an efficient assessment of the longest valid substring. However, in our example, there were no repeated states to determine a valid substring. In a longer string with repeated vowel occurrences, the ans would likely be greater than zero.

Solution Implementation

1from math import inf
2
3class Solution:
4    def findTheLongestSubstring(self, s: str) -> int:
5        # Initialize a list to store the first position we encounter a given state
6        # State is represented as a bitmask integer of size 32 (for 5 vowels, each can be on/off)
7        positions = [inf] * 32
8
9        # The starting state (all vowels have even counts) is at index 0
10        positions[0] = -1
11
12        # List of vowels for reference
13        vowels = 'aeiou'
14
15        # `state` to keep track of the count of vowels encountered (even/odd as a bitmask)
16        # `max_length` to keep track of the length of the longest valid substring so far
17        state = max_length = 0
18
19        # Iterate over the string characters with their index
20        for index, char in enumerate(s):
21            # Check if the current character is a vowel
22            for j, vowel in enumerate(vowels):
23                # Toggle the corresponding bit if we encounter a vowel
24                if char == vowel:
25                    state ^= 1 << j
26
27            # Calculate max length using current index and first index where current state was seen
28            max_length = max(max_length, index - positions[state])
29            # Update the position for this state if it's the first time we're seeing this state
30            positions[state] = min(positions[state], index)
31
32        return max_length
33
1class Solution {
2  
3    // Function to find the length of the longest substring containing vowels in even counts
4    public int findTheLongestSubstring(String s) {
5        // pos array to keep track of the earliest index of each state
6        int[] earliestPos = new int[32]; // 32 possible states for 5 vowels (2^5)
7        // Initialize all positions to max value except for state 0
8        Arrays.fill(earliestPos, Integer.MAX_VALUE);
9        // State 0 (no vowels seen or all seen even times) starts at index -1
10        earliestPos[0] = -1;
11      
12        // String of vowels to check against
13        String vowels = "aeiou";
14      
15        // 'state' will represent the binary value of the vowels seen odd number of times
16        int state = 0;
17        // 'maxLength' stores the length of the longest substring found so far
18        int maxLength = 0;
19      
20        // Loop through characters of input string
21        for (int i = 0; i < s.length(); i++) {
22            char currentChar = s.charAt(i);
23            // Check and flip the corresponding bit for the vowel
24            for (int j = 0; j < 5; j++) {
25                if (currentChar == vowels.charAt(j)) {
26                    state ^= (1 << j);
27                }
28            }
29          
30            // If state has been seen before, update the maxLength
31            maxLength = Math.max(maxLength, i - earliestPos[state]);
32            // If state has not been seen before, set it to the current index
33            if (earliestPos[state] == Integer.MAX_VALUE) {
34                earliestPos[state] = i;
35            }
36        }
37      
38        // Return the length of the longest substring
39        return maxLength;
40    }
41}
42
1class Solution {
2public:
3    int findTheLongestSubstring(string s) {
4        // Initialize a vector to keep track of the first occurrence of all states.
5        vector<int> firstOccurrence(32, INT_MAX);
6        // Setting the base condition that for state '0', the first occurrence is at -1
7        firstOccurrence[0] = -1;
8      
9        // Define a string of vowels for easy indexing.
10        string vowels = "aeiou";
11      
12        // This will keep track of the current state of vowels encountered.
13        int currentState = 0;
14      
15        // The result variable to store the length of the longest substring.
16        int longestSubstringLength = 0;
17      
18        // Iterate over the characters of the string.
19        for (int i = 0; i < s.size(); ++i) {
20            // Check if the current character is a vowel and update the state accordingly.
21            for (int j = 0; j < 5; ++j) { // There are 5 vowels.
22                if (s[i] == vowels[j]) {
23                    // Toggle the j-th bit of the state to represent the occurrence of vowel.
24                    currentState ^= (1 << j);
25                }
26            }
27            // Calculate the length if the current state has occurred before
28            // The length of the valid string would be difference of indices.
29            longestSubstringLength = max(longestSubstringLength, i - firstOccurrence[currentState]);
30            // Update the occurrence of current state if it's the first time.
31            firstOccurrence[currentState] = min(firstOccurrence[currentState], i);
32        }
33      
34        // Return the length of the longest valid substring found.
35        return longestSubstringLength;
36    }
37};
38
1// Define a string of vowels for easy indexing.
2const vowels: string = "aeiou";
3
4// This function calculates and returns the length of the longest substring
5// where the count of each vowel is even.
6function findTheLongestSubstring(s: string): number {
7    // Initialize an array to keep track of the first occurrence of all states.
8    let firstOccurrence: number[] = new Array(32).fill(Number.MAX_SAFE_INTEGER);
9    // Setting the base condition that for state '0', the first occurrence is at -1
10    firstOccurrence[0] = -1;
11  
12    // This will keep track of the current state of vowels encountered.
13    let currentState: number = 0;
14  
15    // The variable to store the length of the longest substring.
16    let longestSubstringLength: number = 0;
17  
18    // Iterate over the characters of the string.
19    for (let i = 0; i < s.length; i++) {
20        // Check if the current character is a vowel and update the state accordingly.
21        for (let j = 0; j < vowels.length; j++) {
22            if (s[i] === vowels[j]) {
23                // Toggle the j-th bit of the state to represent the occurrence of the vowel.
24                currentState ^= (1 << j);
25            }
26        }
27        // If the current state hasn't occurred before, update the occurrence of the current state.
28        if (firstOccurrence[currentState] === Number.MAX_SAFE_INTEGER) {
29            firstOccurrence[currentState] = i;
30        }
31      
32        // Calculate the length if the current state has occurred before
33        // The length of the valid substring would be the difference of indices.
34        longestSubstringLength = Math.max(longestSubstringLength, i - firstOccurrence[currentState]);
35    }
36  
37    // Return the length of the longest valid substring found.
38    return longestSubstringLength;
39}
40
Not Sure What to Study? Take the 2-min Quiz：

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

Time and Space Complexity

Time Complexity

The given code iterates over each character of the string s, which has a length n. It performs a constant amount of work for each character: checking if the character is a vowel, possibly flipping a bit in the state variable, and updating ans and pos[state]. Because these operations all have a constant time complexity, the overall time complexity of the function is O(n).

Space Complexity

The space complexity is determined by the fixed-size array pos, which has 32 elements (one for each possible state of the 5 vowel bits), and a few additional integer variables (state, ans, and the loop variables). Therefore, the space complexity of the algorithm is O(1) since the space required does not grow with the size of the input string s.

Learn more about how to find time and space complexity quickly using problem constraints.

Fast Track Your Learning with Our Quick Skills Quiz:

What are the most two important steps in writing a depth first search function? (Select 2)

Recommended Readings

Prefix Sum

Prefix Sum The prefix sum is an incredibly powerful and straightforward technique Its primary goal is to allow for constant time range sum queries on an array What is Prefix Sum The prefix sum of an array at index i is the sum of all numbers from index 0 to i By

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 👨‍🏫