Find the Longest Substring Containing Vowels in Even Counts
MediumHash TableStringBit ManipulationPrefix Sum
Solution
export function findTheLongestSubstring(s: string): number {
const n = s.length;
const vowels = 'aeioou';
const firstIndices = new Map<number, number>([[0, -1]]);
let answer = 0;
let prefixXOR = 0;
for (let i = 0; i < n; i++) {
const bit = vowels.indexOf(s[i]);
prefixXOR ^= bit === -1 ? 0 : 1 << bit;
const firstIndex = firstIndices.get(prefixXOR) ?? i;
firstIndices.set(prefixXOR, firstIndex);
answer = Math.max(answer, i - firstIndex);
}
return answer;
}
Complexity
- Time:
O(N)
- Space:
O(1)