Solution: Find the Longest Substring Having Vowels in Even Counts
Statement▼
Given the string s, return the length of the longest
Constraints:
1≤ s.length≤5×103 scontains only lowercase English letters.
Solution
It’s important to note that we only need to know whether each vowel appears an even or odd number of times in any substring—we don’t need the exact counts. This is where bitwise operations can help. In bitwise terms, we use XOR on its bits to check if a value occurs an even or odd number of times (its parity). If the result of XOR is 1, the value has occurred an odd number of times; if it’s 0, it’s even. We’ll apply this idea to the characters in the input string: each vowel is represented by a bit, and as we process each character, we’ll use XOR with a fixed-size bitmask to track whether it has an even or odd count.
Each vowel is assigned a unique bit in a binary number. Because there are 5 vowels, the first five bits are enough to represent them. We place 'a' in the first bit, 'e' in the second bit, and so on.
The remaining characters are assigned an integer value of 0 (binary 00000) because we don't need to track their parity. The input string, when converted to its binary representation, will look like this:
Because we only need to focus on the parity of vowels, we use a bitmask of five bits, where each bit represents a vowel. Using the XOR operation, the bit is toggled each time the corresponding vowel appears. As we traverse the string, we maintain a running XOR value (the state of bitmask at any given point, let's call it prefix XOR), which updates with each character processed. If we encounter a vowel, the corresponding bit in the prefix XOR is flipped, indicating an odd count; if we encounter that vowel again, the bit is flipped back, indicating an even count.
That was about checking the parity of vowels, but now, how do we identify the longest substring with an even count of vowels? For this, we'll use the fact that if a bit's state returns to its original state (meaning it changes from 0 to 1 and then back to 0), it indicates that the corresponding vowel has occurred an even number of times. If the bit's state doesn’t return to its original state, the vowel has occurred an odd number of times. We'll apply this concept to our bitmask's state and keep the following pointers in mind:
If the current XOR value for ...
Solution: Find the Longest Substring Having Vowels in Even Counts
Statement▼
Given the string s, return the length of the longest
Constraints:
1≤ s.length≤5×103 scontains only lowercase English letters.
Solution
It’s important to note that we only need to know whether each vowel appears an even or odd number of times in any substring—we don’t need the exact counts. This is where bitwise operations can help. In bitwise terms, we use XOR on its bits to check if a value occurs an even or odd number of times (its parity). If the result of XOR is 1, the value has occurred an odd number of times; if it’s 0, it’s even. We’ll apply this idea to the characters in the input string: each vowel is represented by a bit, and as we process each character, we’ll use XOR with a fixed-size bitmask to track whether it has an even or odd count.
Each vowel is assigned a unique bit in a binary number. Because there are 5 vowels, the first five bits are enough to represent them. We place 'a' in the first bit, 'e' in the second bit, and so on.
The remaining characters are assigned an integer value of 0 (binary 00000) because we don't need to track their parity. The input string, when converted to its binary representation, will look like this:
Because we only need to focus on the parity of vowels, we use a bitmask of five bits, where each bit represents a vowel. Using the XOR operation, the bit is toggled each time the corresponding vowel appears. As we traverse the string, we maintain a running XOR value (the state of bitmask at any given point, let's call it prefix XOR), which updates with each character processed. If we encounter a vowel, the corresponding bit in the prefix XOR is flipped, indicating an odd count; if we encounter that vowel again, the bit is flipped back, indicating an even count.
That was about checking the parity of vowels, but now, how do we identify the longest substring with an even count of vowels? For this, we'll use the fact that if a bit's state returns to its original state (meaning it changes from 0 to 1 and then back to 0), it indicates that the corresponding vowel has occurred an even number of times. If the bit's state doesn’t return to its original state, the vowel has occurred an odd number of times. We'll apply this concept to our bitmask's state and keep the following pointers in mind:
If the current XOR value for ...