1371

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.

Companies:
Microsoft

Related Topics:
Hash Table, String, Bit Manipulation, Prefix Sum

Solution 1. Bitmask + Prefix State Map

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 as have been visited, substring s[0..i] is valid.

For i = 13 ~ 16, 3 as have been visited, substring s[5..i] is valid.

For i = 17 ~ (N - 1), 4 as 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, substring s[0..i] is valid which has length i + 1.
• If we've visited odd number of a, substring s[(k+1)..i] is valid where k is the first index of the first occurrence of a. The length is i - 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 index i, find the index of the first occurrence of the same state x, say k, then i - k is the length of the longest valid string ending at i.

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 mask of s[i] first, then:

• If we've seen this state, then try to update the answer using i - index[mask].
• Otherwise, index[mask] = i.

// OJ: https://leetcode.com/problems/find-the-longest-substring-containing-vowels-in-even-counts/
// Author: github.com/lzl124631x
// 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;
    }
};