Find the Longest Substring Containing Vowels in Even Counts — LeetCode 1371 Python Solution
MediumBit ManipulationHash TableStringPrefix Sum
- Problem
- #1371
- Pattern
- Prefix Sum
- Reading time
- 2 min
- Source
- leetcode.com
The problem
Given the string s, return the size of the longest substring containing each vowel an even number of times. That is, 'a', 'e', 'i', 'o', and 'u' must appear an even number of times.
Example
- Input
- s = "eleetminicoworoep"
- Output
- 13
- Explanation
- The longest substring is "leetminicowor" which contains two each of the vowels: e, i and o and zero of the vowels: a and u.
Python solution
Python
class Solution:
def findTheLongestSubstring(self, s: str) -> int:
d = {0: -1}
ans = mask = 0
for i, c in enumerate(s):
if c in "aeiou":
mask ^= 1 << (ord(c) - ord("a"))
if mask in d:
j = d[mask]
ans = max(ans, i - j)
else:
d[mask] = i
return ansComplexity
| Measure | Complexity |
|---|---|
| Time | O(n), where n is the length of the string \textit{s} |
| Space | O(1) auxiliary |
Pattern: Prefix Sum
Precompute running totals once so any range query becomes a single subtraction. LeetCode 1371. Find the Longest Substring Containing Vowels in Even Counts is filed here because LeetCode tags it Prefix Sum, which is the vocabulary this hub collects.
The prefix sum guide has the Python template for the pattern and the 157 LeetCode problems that use it.
Related problems
Frequently asked questions
- How hard is LeetCode 1371. Find the Longest Substring Containing Vowels in Even Counts?
- LeetCode 1371. Find the Longest Substring Containing Vowels in Even Counts is rated Medium on LeetCode.
- What is the time complexity of LeetCode 1371. Find the Longest Substring Containing Vowels in Even Counts?
- The Python solution on this page runs in O(n), where n is the length of the string \textit{s}.
- What is the space complexity of LeetCode 1371. Find the Longest Substring Containing Vowels in Even Counts?
- The Python solution on this page uses O(1) auxiliary space.
- What topics does LeetCode 1371. Find the Longest Substring Containing Vowels in Even Counts cover?
- LeetCode 1371. Find the Longest Substring Containing Vowels in Even Counts is tagged Bit Manipulation, Hash Table, String and Prefix Sum on LeetCode.