1371. Find the Longest Substring Containing Vowels in Even Counts
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.
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 is20
in decimal. -
Tracking States: The
state
variable is a 5-bit integer representing the current state of vowels' counts (even/odd). The initial state is0
since we start with an even count (zero occurrences) for all vowels. -
Index Memory (
pos
): An array calledpos
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 withinf
, except forpos[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
, wherej
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 updateans
.
-
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 inpos[state]
, we updatepos[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:
s = "eleetminicoworoep"
- We start at
state = 0
andpos[0] = -1
because we have an even count (zero) for all vowels at the start. - Iterating over
s
, whenever we encounter a vowel, we updatestate
. Supposestate
becomes3
after some operations; this means 'a' and 'e' have been seen an odd number of times so far. - If
state
is3
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.
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 illustrate the solution approach using the string:
s = "aeiobcdf"
-
Initialize the
pos
array with length32
to represent all possible states of vowel occurrences (2^5 for 5 vowels). Set all values toinf
, exceptpos[0]
to-1
. -
We start with
state = 0
(since no vowels have been seen yet) andans = 0
(since no substrings have been found yet). -
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 thestate
is toggled from0
to1
. 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 remains01111
. - At index 5,
s[5] = 'c'
: 'c' is not a vowel; state remains01111
. - At index 6,
s[6] = 'd'
: 'd' is not a vowel; state remains01111
. - At index 7,
s[7] = 'f'
: 'f' is not a vowel; state remains01111
.
- When at index 0,
-
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
. -
Throughout our iteration, the state has changed from
00000
to01111
. After toggling the bits whenever we encountered a vowel, we checkedpos
to see if the current state had been recorded before. In this instance, since no state repeated other than the initial state0
, the length of the longest valid substring is zero because we have not encountered a state twice where the state would be00000
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
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.
What are the two properties the problem needs to have for dynamic programming to be applicable? (Select 2)
Recommended Readings
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 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!