NeetCode #878LC-1371MediumBit Manipulation
← Back to All Problems#878 · #1371 · Find the Longest Substring Containing Vowels in Even Counts(每个元音包含偶数次的最长子字符串)
📌 Problem Statement & Constraints
Given a string
s, return the length of the longest substring in which each of the vowels a, e, i, o, u occurs an even number of times. Constraints: 1 <= s.length <= 5 * 10^5, and s consists only of lowercase English letters.💡 Core Algorithmic Approaches
- Only the parity of each vowel's count matters, which is captured by a 5-bit mask.
- Scan the string while maintaining the running parity mask; two positions with the same mask bound a substring where every vowel count is even.
- Record the first index at which each mask appears; the longest valid substring ending at the current index is the distance to that first occurrence.
- Seed the mask 0 at index -1 so that substrings starting at index 0 are counted.
💻 Benchmark Python3 Implementation
class Solution:
def findTheLongestSubstring(self, s: str) -> int:
vowels = "aeiou"
first = {0: -1} # mask -> earliest index seen
mask = 0
best = 0
for i, ch in enumerate(s):
if ch in vowels:
mask ^= 1 << vowels.index(ch) # flip that vowel's parity bit
if mask in first:
best = max(best, i - first[mask])
else:
first[mask] = i
return best⚡ Complexity Deep Dive
⏱️ Time Complexity
O(n): one pass with a fixed 32-entry map.
💾 Space Complexity
O(32) = O(1): the mask-to-index map.
⚠️ Interview Pitfalls & Follow-ups
- Tracking the full vowel counts instead of their parities: only the parity matters, so a 5-bit mask is enough.
- Forgetting to seed mask 0 at index -1: a substring starting at index 0 with all even counts would be missed.
- Storing the latest index for each mask instead of the earliest: the earliest occurrence maximises the length.
- Allocating a bit to every letter: only the five vowels change the mask, so consonants must be skipped.
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.