What is the brute force approach and complexity for Longest Substring Containing Vowels in Even Counts?

Fix each start, grow the end while tracking vowel parities, check all even with time complexity O(N²) and space complexity O(1).

What is the optimal approach and complexity for Longest Substring Containing Vowels in Even Counts?

Same parity mask seen before ⇒ every vowel is even in between; store the first index of each of the 32 masks with optimal time complexity O(N) and space complexity O(1).

How do you identify the pattern for Longest Substring Containing Vowels in Even Counts?

Look for key signals in the prompt: "longest substring" indicates A contiguous range, and we want the farthest-left start for each end → store the first index.; "each vowel appears an even number of times" indicates Only parity matters → one bit per vowel, flip with XOR.; "five vowels" indicates 5 bits → only 32 possible states → an array of 32 instead of a hash map..

Longest Substring Containing Vowels in Even Counts

Medium·LeetCode #1371 Pro OnlySlight Variation

LeetCode

Problem Statement

You are given a string s of lowercase letters.

Find the longest contiguous substring in which each vowel — a, e, i, o, u — appears an even number of times, and return its length. Zero times counts as even, so a substring with no vowels at all is fine.

Input

A string s of lowercase English letters.

Output

The length of the longest substring where every vowel count is even.

Example 1

Input: s = "eleetminicoworoep"

Output: 13

"leetminicowor" has e×2, i×2, o×2 and no a or u. Every count is even.

Example 2

Input: s = "leetcodeisgreat"

Output: 5

"leetc" has e×2 and no other vowels.

Example 3

Input: s = "bcbcbc"

Output: 6

There are no vowels at all, so every count is 0 (even). The whole string works.

Constraints

• 1 ≤ s.length ≤ 5 · 10^5
• s contains only lowercase English letters

Pattern Recognition Clues

Recognising these key signals in the problem description immediately identifies the pattern:

“longest substring”

→ A contiguous range, and we want the farthest-left start for each end → store the first index.

“each vowel appears an even number of times”

→ Only parity matters → one bit per vowel, flip with XOR.

“five vowels”

→ 5 bits → only 32 possible states → an array of 32 instead of a hash map.

Approach Complexity Ladder

Brute Force — try every startO(N²)O(1)

Fix each start, grow the end while tracking vowel parities, check all even

Optimal — prefix parity mask + first indexO(N)O(1)

Same parity mask seen before ⇒ every vowel is even in between; store the first index of each of the 32 masks

Brute Force Intuition

For every start, walk the end to the right. Keep a small mask of which vowels are odd so far in s[start..end]. When the mask is 0, every vowel is even, so update the best length.

Recognition rule for this sub-pattern:

Turn values into +1/−1 (or bit flags) so "balanced" means "same prefix state seen before". Store the first index of each state.

Remember this · Prefix Sum

Trigger

Range sums, "subarray sum equals K" (especially with negatives), equal counts, divisible by K.

Think

If I knew the total up to every index, would the answer become a difference of two totals?

Key question

Which earlier prefix value am I looking for when I stand at index i?

Brute2Best Pro Content

Unlock Complete Visual Walkthrough & Optimal C++

The interactive animated dry-run player, optimized C++ implementation, state invariant derivations, and edge-case breakdown for this question are part of Brute2Best Pro. The anchor question of every sub-pattern is completely free.

All 440 visual dry runs & algorithms

Interactive step-by-step playback with pointer & array state transitions

52 comprehensive LLD chapters

Interactive UML diagrams, real-world stories (Food Delivery, Trading, RPG), and practice solutions

40 C++ basics labs & hardware memory models

Vtables, byte layouts, assembly insights, and multi-threading race conditions

Production-ready C++23 source code

Modern idioms, clean contracts, time/space complexity derivations, and interview takeaways

Create Free Account Log in

First anchor question per pattern, Part 1 LLD & Module 1 C++ basics are 100% Free forever.

Beyond The LeetCode Problem

How this concept connects to System Design & C++ Systems

Bridge DSA with production engineering

Top engineering interviews test whether you understand how algorithms like Prefix Sum translate into production architectures and low-level memory mechanics.

LLD Architecture