Welcome to Subscribe On Youtube
Formatted question description: https://leetcode.ca/all/1371.html
1371. Find the Longest Substring Containing Vowels in Even Counts (Medium)
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 1:
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.
Example 2:
Input: s = "leetcodeisgreat" Output: 5 Explanation: The longest substring is "leetc" which contains two e's.
Example 3:
Input: s = "bcbcbc" Output: 6 Explanation: In this case, the given string "bcbcbc" is the longest because all vowels: a, e, i, o and u appear zero times.
Constraints:
1 <= s.length <= 5 x 10^5
s
contains only lowercase English letters.
Related Topics: String
Solution 1. Greedy + State Compression
At the first glance it’s like a sliding window problem. For a find maximum sliding window problem, the initial state should be valid, then keep extending the 2nd pointer until the state becomes invalid (now the maximum is found), then move the first pointer to get back the valid state again.
In this problem, the initial state is valid. When extending the 2nd pointer, the state might jump back and forth between invalid and valid before reaching the longest valid end position. So we shouldn’t use sliding window to solve this problem.
Try to get the intuition by simplying the problem – what if we only consider a
as vowel?
4 9 13 17
v v v v
xxxxaxxxxaxxxaxxxaxxx
~
1
4
1
Consider the above input.
For i = 0 ~ 3
, 0
a
has been visited, substring s[0..i]
is valid.
For i = 4 ~ 8
, 1
a
has been visited, substring s[5..i]
is valid.
For i = 9 ~ 12
, 2
a
s have been visited, substring s[0..i]
is valid.
For i = 13 ~ 16
, 3
a
s have been visited, substring s[5..i]
is valid.
For i = 17 ~ (N  1)
, 4
a
s have been visited, substring s[0..i]
is valid.
So we can see there can be a greedy solution:
 If we’ve visited even number of
a
, substrings[0..i]
is valid which has lengthi + 1
.  If we’ve visited odd number of
a
, substrings[(k+1)..i]
is valid wherek
is the first index of the first occurrence ofa
. The length isi  k
.
We can regard even and odd are two different states, then the above two cases can be unified into one:
 If we are in state
x
at indexi
, find the index of the first occurrence of the same statex
, sayk
, theni  k
is the length of the longest valid string ending ati
.
Note that we need to regard 1
as the index of the first occurrence of even state.
Now we consider the 5 vowels. Each vowel has two different states, even and odd. So in total there are 2^5
different states. We can use bitmask to encode the state.
For example, if the state of aeiou
are even, even, odd, odd, even respectively, we can encode the state as 00110
.
Let index
be a map from state x
to the index of the first occurrence of state x
.
For each index i
, we get the corresponding state h
of s[i]
first, then:
 If we’ve seen this state, then try to update the answer using
i  index[h]
.  Otherwise,
m[h] = i
.
// OJ: https://leetcode.com/problems/findthelongestsubstringcontainingvowelsinevencounts/
// Time: O(N)
// Space: O(1)
class Solution {
public:
int findTheLongestSubstring(string s) {
int h = 0, ans = 0;
unordered_map<int, int> m{ {'a',0},{'e',1},{'i',2},{'o',3},{'u',4} }, index{ {0,1} };
for (int i = 0; i < s.size(); ++i) {
if (m.count(s[i])) h ^= 1 << m[s[i]];
if (index.count(h)) ans = max(ans, i  index[h]);
else index[h] = i;
}
return ans;
}
};

class Solution { public int findTheLongestSubstring(String s) { int[] map = new int[32]; Arrays.fill(map, 1); int state = 0; map[state] = 0; int maxLength = 0; int length = s.length(); for (int i = 0; i < length; i++) { char c = s.charAt(i); if (c == 'a') state ^= (1 << 0); else if (c == 'e') state ^= (1 << 1); else if (c == 'i') state ^= (1 << 2); else if (c == 'o') state ^= (1 << 3); else if (c == 'u') state ^= (1 << 4); if (map[state] >= 0) maxLength = Math.max(maxLength, i + 1  map[state]); else map[state] = i + 1; } return maxLength; } } ############ class Solution { public int findTheLongestSubstring(String s) { int[] pos = new int[32]; Arrays.fill(pos, Integer.MAX_VALUE); pos[0] = 1; String vowels = "aeiou"; int state = 0; int ans = 0; for (int i = 0; i < s.length(); ++i) { char c = s.charAt(i); for (int j = 0; j < 5; ++j) { if (c == vowels.charAt(j)) { state ^= (1 << j); } } ans = Math.max(ans, i  pos[state]); pos[state] = Math.min(pos[state], i); } return ans; } }

// OJ: https://leetcode.com/problems/findthelongestsubstringcontainingvowelsinevencounts/ // Time: O(N) // Space: O(1) class Solution { public: int findTheLongestSubstring(string s) { int h = 0, ans = 0; unordered_map<int, int> m{ {'a',0},{'e',1},{'i',2},{'o',3},{'u',4} }, index{ {0,1} }; for (int i = 0; i < s.size(); ++i) { if (m.count(s[i])) h ^= 1 << m[s[i]]; if (index.count(h)) ans = max(ans, i  index[h]); else index[h] = i; } return ans; } };

class Solution: def findTheLongestSubstring(self, s: str) > int: pos = [inf] * 32 pos[0] = 1 vowels = 'aeiou' state = ans = 0 for i, c in enumerate(s): for j, v in enumerate(vowels): if c == v: state ^= 1 << j ans = max(ans, i  pos[state]) pos[state] = min(pos[state], i) return ans

func findTheLongestSubstring(s string) int { pos := make([]int, 32) for i := range pos { pos[i] = math.MaxInt32 } pos[0] = 1 vowels := "aeiou" state, ans := 0, 0 for i, c := range s { for j, v := range vowels { if c == v { state ^= (1 << j) } } ans = max(ans, ipos[state]) pos[state] = min(pos[state], i) } return ans } func max(a, b int) int { if a > b { return a } return b } func min(a, b int) int { if a < b { return a } return b }