1371. Find the Longest Substring Containing Vowels in Even Counts

Given the string s, return the size of the longest substring containing each vowel an even number of times. That is, ‘a’, ‘e’, ‘i’, ‘o’, and ‘u’ must appear an even number of times.

Example 1:

Input: s = "eleetminicoworoep"
Output: 13
Explanation: The longest substring is "leetminicowor" which contains two each of the vowels: e, i and o and zero of the vowels: a and u.

Example 2:

Input: s = "leetcodeisgreat"
Output: 5
Explanation: The longest substring is "leetc" which contains two e's.

Example 3:

Input: s = "bcbcbc"
Output: 6
Explanation: In this case, the given string "bcbcbc" is the longest because all vowels: a, e, i, o and u appear zero times.

Constraints:

• 1 <= s.length <= 5 x 10^5
• s contains only lowercase English letters.

Approach 01:

class Solution {
public:
    int findTheLongestSubstring(string s) {
        constexpr string_view vowels = "aeiou";
        int maxLength = 0;
        int binaryPrefix = 0;  // Binary representation of vowel counts
        unordered_map<int, int> prefixToIndex{{0, -1}};  // Stores the first occurrence of each binary prefix

        // Iterate through the string
        for (int i = 0; i < s.length(); ++i) {
            const int vowelIndex = vowels.find(s[i]);
            // If the current character is a vowel, update the binary prefix
            if (vowelIndex != -1) {
                binaryPrefix ^= 1 << vowelIndex;
            }
            // If the binary prefix hasn't been seen before, record its index
            if (!prefixToIndex.contains(binaryPrefix)) {
                prefixToIndex[binaryPrefix] = i;
            }
            // Calculate the length of the current substring
            maxLength = max(maxLength, i - prefixToIndex[binaryPrefix]);
        }

        return maxLength;
    }
};

class Solution:
    def findTheLongestSubstring(self, s: str) -> int:
        vowels = "aeiou"
        maxLength = 0
        binaryPrefix = 0  # The binary representation of vowel counts
        prefixToIndex = {0: -1}  # Stores the first occurrence of each binary prefix

        # Iterate through the string
        for i, char in enumerate(s):
            vowelIndex = vowels.find(char)
            # If the current character is a vowel, update the binary prefix
            if vowelIndex != -1:
                binaryPrefix ^= 1 << vowelIndex
            # If the binary prefix hasn't been seen before, record its index
            if binaryPrefix not in prefixToIndex:
                prefixToIndex[binaryPrefix] = i
            # Calculate the length of the current substring
            maxLength = max(maxLength, i - prefixToIndex[binaryPrefix])

        return maxLength

Time Complexity

• Iterating through the string:

  The algorithm iterates through each character of the string s. Given that the length of the string is n, this step takes \(O(n)\).

• Updating the binary prefix:

  For each character, checking if it’s a vowel and updating the binary prefix involves looking up the index of the character in the vowel string (constant time \(O(1)\)) and performing a bitwise XOR (also \(O(1)\)). This operation is repeated for each character, so the total time for this part is \(O(n)\).

• Checking and updating the map:

  For each binary prefix, the algorithm checks and possibly updates the map, which is an \(O(1)\) operation on average. This step is repeated for each character, contributing \(O(n)\) to the total time complexity.

• Overall Time Complexity:

  The overall time complexity is \(O(n)\), where n is the length of the input string s.

Space Complexity

• Space for the map:

  The unordered map prefixToIndex stores at most 32 entries, as there are only 32 possible states for the binary prefix (5 vowels). Therefore, the space complexity for the map is \(O(1)\).

• Space for other variables:

  The space for variables such as maxLength, binaryPrefix, and the constant string vowels is \(O(1)\).

• Overall Space Complexity:

  The overall space complexity is \(O(1)\), since the extra space used does not grow with the size of the input string.