Leetcode 1371: Find the Longest Substring Containing Vowels in Even Counts

 https://leetcode.com/problems/find-the-longest-substring-containing-vowels-in-even-counts/description/

Notes:

This question can be solved by a method similar to "how many sub-array sum equals to a target value". If you have question about this, we can go step by step.

The naive method is to scan all the sub-strings, and then check the counts in each sub-string, and find the longest one. This needs O(n^2) time, so this is the upper-bound for this question.

Actually the largest case is n = 5 x 10^5, so we need a better method.

Let think about one letter only: what is the longest sub-string containing even count of one specific letter?

There are many ways to do this, but in order to achieve O(n) time complexity, we can use a bit to represents the count of the letter: 0 for even, 1 for odd. Then as we scan through the string, at each position, we know the count is even or odd. 

If even: the current longest sub-string is from the first even to the current position;

if odd:  the current longest sub-string is from the first odd to the current position.

Now, we need to monitor five letters, but the idea is the same. We just use a bit mask to replace one bit.

If we use a bit mask to record the counts of each letter; 0 for even, 1 for odd, then when the mask appear again, the sub-string between these two mask should contain even number of each letter.

One hash-map can be used to record the position (or index) of each mask when it appears for the first time, since we need this information to calculate the length of the current longest valid sub-string.

See the code below:

class Solution {
public:
    int findTheLongestSubstring(string s) {
        int res = 0, n = s.size(), mask = 0;
        vector<int> dp(1<<5, s.size());// only 5 letters, so 5 bits
        dp[0] = -1;// special case for boundary condition
        for(int i=0; i<n; ++i) {
            char a = s[i];
            if(a=='a') mask ^= 1<<0;
            else if(a=='e') mask ^= 1<<1;
            else if(a=='i') mask ^= 1<<2;
            else if(a=='o') mask ^= 1<<3;
            else if(a=='u') mask ^= 1<<4;
            res = max(res, i - dp[mask]);
            dp[mask] = min(i, dp[mask]);// record the first position
        }
        return res;
    }
};