Find the Longest Substring Containing Vowels in Even Counts

Find the Longest Substring Containing Vowels in Even Counts - Problem

Given a string s, return the length of the longest substring containing each vowel ('a', 'e', 'i', 'o', 'u') an even number of times.

A substring is a contiguous sequence of characters within a string. For the substring to be valid, every vowel must appear an even number of times (including zero times).

Note: Consonants can appear any number of times and don't affect the validity of the substring.

Input & Output

Example 1 — Basic Case

$ Input: s = "eleetminicoworoep"

› Output: 13

💡 Note: The substring "leetminicoworoep" contains: a:0, e:4, i:2, o:4, u:0. All vowels appear an even number of times, giving length 13.

Example 2 — No Vowels

$ Input: s = "bcbcbc"

› Output: 6

💡 Note: The entire string has no vowels, so all vowels appear 0 times (even). The full length 6 is the answer.

Example 3 — All Odd Counts

$ Input: s = "aeiou"

› Output: 0

💡 Note: Each vowel appears exactly once (odd count). No valid substring exists where all vowels have even counts.

Constraints

1 ≤ s.length ≤ 5 × 10⁴
s consists of lowercase English letters only

Visualization

Tap to expand

Understanding the Visualization

Input Analysis

String "eleetminicoworoep" with vowels to track

State Tracking

Track vowel count parity using bitmask

Result

Find longest substring with all even vowel counts

Key Takeaway

🎯 Key Insight: Use bitmask to track vowel parity - when same pattern repeats, substring between has all even vowel counts

Asked in

f Facebook 8 a Amazon 5 M Microsoft 3

The key insight is using bit manipulation to track vowel parity states efficiently. When the same parity pattern repeats, the substring between those positions has all even vowel counts. Best approach uses bitmask with hash map in O(n) time and O(n) space.

Common Approaches

Approach	Time	Space	Notes
✓ Bit Manipulation with Prefix States	O(n)	O(n)	Use bitmask to track vowel parity and find matching states
Brute Force - Check All Substrings	O(n³)	O(1)	Generate all possible substrings and count vowels in each
Prefix Sum with State Mapping	O(n)	O(n)	Track cumulative vowel counts and find positions with same parity pattern

Bit Manipulation with Prefix States — Algorithm Steps

Initialize mask = 0 and store position -1
For each character, toggle corresponding vowel bit
If mask seen before, calculate substring length
Update maximum length found

Visualization

Tap to expand

Step-by-Step Walkthrough

Initialize

Start with mask=0, store position -1

Toggle Bits

XOR corresponding vowel bit for each character

Find Matches

When mask repeats, calculate substring length

Code -

solution.c — C

#include <stdio.h>
#include <string.h>
#include <stdlib.h>

#define MAX_STATES 32

struct HashEntry {
    int mask;
    int position;
    int valid;
};

int hash(int mask) {
    return mask % MAX_STATES;
}

int findPosition(struct HashEntry* table, int mask) {
    int h = hash(mask);
    for (int i = 0; i < MAX_STATES; i++) {
        int idx = (h + i) % MAX_STATES;
        if (!table[idx].valid) return -1;
        if (table[idx].mask == mask) return table[idx].position;
    }
    return -1;
}

void insertPosition(struct HashEntry* table, int mask, int position) {
    int h = hash(mask);
    for (int i = 0; i < MAX_STATES; i++) {
        int idx = (h + i) % MAX_STATES;
        if (!table[idx].valid) {
            table[idx].mask = mask;
            table[idx].position = position;
            table[idx].valid = 1;
            return;
        }
    }
}

int getVowelBit(char c) {
    switch(c) {
        case 'a': return 0;
        case 'e': return 1;
        case 'i': return 2;
        case 'o': return 3;
        case 'u': return 4;
        default: return -1;
    }
}

int solution(char* s) {
    struct HashEntry maskPositions[MAX_STATES] = {0};
    insertPosition(maskPositions, 0, -1); // Empty prefix has mask 0
    
    int mask = 0;
    int maxLen = 0;
    int n = strlen(s);
    
    for (int i = 0; i < n; i++) {
        int bit = getVowelBit(s[i]);
        if (bit != -1) {
            mask ^= (1 << bit);
        }
        
        int pos = findPosition(maskPositions, mask);
        if (pos != -1) {
            int length = i - pos;
            if (length > maxLen) {
                maxLen = length;
            }
        } else {
            insertPosition(maskPositions, mask, i);
        }
    }
    
    return maxLen;
}

int main() {
    char s[100001];
    fgets(s, sizeof(s), stdin);
    s[strcspn(s, "\n")] = 0;
    int result = solution(s);
    printf("%d\n", result);
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n)

Single pass through string with O(1) operations per character

✓ Linear Growth

Space Complexity

O(n)

Hash map stores up to n different mask states

⚡ Linearithmic Space

22.9K Views

Medium Frequency

~25 min Avg. Time

847 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Bit Manipulation with Prefix States — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler