#1371

Medium

LeetCode Problem Workspace

Find the Longest Substring Containing Vowels in Even Counts

Find the longest substring with even counts of vowels using bitmasking and hash tables.

hash table string bit manipulation prefix sum

Problem Statement

You are given a string s, and your task is to find the length of the longest substring in which every vowel ('a', 'e', 'i', 'o', 'u') appears an even number of times. A vowel is considered to have an even count when its occurrences are divisible by 2. The string only contains lowercase English letters.

To solve this problem efficiently, we need to track the parity of vowel counts as we progress through the string. This can be done using bit manipulation. Each bit in an integer will represent whether the corresponding vowel has an odd or even count. Using a hash table to store the first occurrence of each bitmask will help in calculating the length of the longest valid substring.

Examples

Example 1

Input: s = "eleetminicoworoep"

Output: 13

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

The longest substring is "leetc" which contains two e's.

Example 3

Input: s = "bcbcbc"

Output: 6

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.

Solution Approach

Bitmask Representation

Each vowel ('a', 'e', 'i', 'o', 'u') is mapped to a bit in an integer. As you traverse the string, flip the corresponding bit to track whether the vowel count is odd or even. A bit of '1' represents an odd count, while '0' represents an even count.

Hash Table for First Occurrence

Use a hash table to store the first occurrence of each bitmask. If the same bitmask appears again later, it indicates that the substring between these two occurrences contains an even number of each vowel.

Maximize Substring Length

For each character in the string, calculate the current bitmask. Check the hash table for the first occurrence of this bitmask, and calculate the length of the valid substring. Keep track of the maximum length.

Complexity Analysis

Metric	Value
Time	O(n)
Space	O(1)

The time complexity is O(n) because we are iterating through the string once and performing constant-time operations (hash table lookups and bit manipulations) for each character. The space complexity is O(1) since the bitmask only requires a fixed amount of space (32 bits for tracking vowels). The hash table stores at most 32 entries, making the space requirement constant in practice.

What Interviewers Usually Probe

The candidate uses bit manipulation effectively to represent the parity of vowel counts.
The candidate applies hash tables to optimize the search for the longest valid substring.
The candidate avoids using brute-force approaches that would lead to O(n^2) time complexity.

Common Pitfalls or Variants

Common pitfalls

Overcomplicating the problem by using nested loops instead of a linear pass with bit manipulation.
Failing to initialize the hash table properly and missing the base case where no vowels are encountered.
Not recognizing that the problem only involves vowel counts and misusing the bitmask for non-vowel characters.

Follow-up variants

Modify the problem to count vowels that appear an odd number of times instead of even.
Extend the problem to include uppercase vowels and ensure case insensitivity.
Allow other characters (e.g., punctuation) and ask for substrings with even vowel counts, ignoring non-alphabet characters.

FAQ

What is the primary pattern used in the 'Find the Longest Substring Containing Vowels in Even Counts' problem?

The primary pattern used in this problem is hash table plus bit manipulation. The problem is solved by tracking the parity of vowel counts using a bitmask, and hash tables are used to store the first occurrence of each bitmask.

How do you track vowel counts in the 'Find the Longest Substring Containing Vowels in Even Counts' problem?

Vowel counts are tracked using a bitmask, where each bit represents whether a specific vowel count is odd or even. By flipping the corresponding bit as you encounter each vowel, you can efficiently track the parity of the vowel counts.

Why is a hash table used in this problem?

The hash table stores the first occurrence of each bitmask, allowing us to calculate the length of the longest valid substring. By checking for repeated bitmasks, we can find substrings with even counts of vowels in linear time.

What is the time complexity of the 'Find the Longest Substring Containing Vowels in Even Counts' problem?

The time complexity is O(n), where n is the length of the string. This is because we iterate through the string once, performing constant-time operations for each character.

What are the key advantages of using bitmasking for this problem?

Bitmasking allows us to efficiently track the parity of each vowel count with constant space, and it avoids the need for nested loops or brute-force checks, ensuring the solution runs in linear time.

terminal

Solution

Solution 1: Prefix XOR + Array or Hash Table

According to the problem description, if we use a number to represent the parity of the occurrences of each vowel in a prefix of the string $\textit{s}$, then when two prefixes have the same number, the substring between these two prefixes is a valid substring.

1

2

3

4

5

6

7

8

9

10

11

12

13

class Solution:
    def findTheLongestSubstring(self, s: str) -> int:
        d = {0: -1}
        ans = mask = 0
        for i, c in enumerate(s):
            if c in "aeiou":
                mask ^= 1 << (ord(c) - ord("a"))
            if mask in d:
                j = d[mask]
                ans = max(ans, i - j)
            else:
                d[mask] = i
        return ans

Continue Practicing

#1177 can make palindrome from substring #1442 count triplets that can form two arrays of equal xor #1525 number of good ways to split a string