⚡Flashcard Drill➔
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

  1. Only the parity of each vowel's count matters, which is captured by a 5-bit mask.
  2. Scan the string while maintaining the running parity mask; two positions with the same mask bound a substring where every vowel count is even.
  3. 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.
  4. 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.
🎯 Drill This Card Now➔

🧩 Related Bit Manipulation Problems