Leetcode 1542: Find Longest Awesome Substring

 https://leetcode.com/problems/find-longest-awesome-substring/description/

Notes:

This question is similar to another question, Leetcode 1371

The basic idea is the same: use a mask to memorize the counting of each letters. In this question, the letters are numbers from 0 to 9. 

Then we need to know whether the counting of each letter is even or odd. So we can use a bit to indicate this. For each bit, 0 means even count; 1 means odd.

If the same mask shows up again, then the substring between these two masks should have even numbers of every letter; and this is what we need to construct a palindrome.

Another possible situation for a palindrome is to have one letter with odd counting. This can also be checked by add one more letter (for each kind) to the mask.

See the code below:

class Solution {
public:
    int longestAwesome(string s) {
        int n = s.size(), res = 0, mask = 0;
        vector<int> dp(1<<10, -2);
        dp[0] = -1;
        for(int i=0; i<n; ++i) {
            mask ^= 1<<(s[i] - '0');
            if(dp[mask] != -2) res = max(res, i - dp[mask]);
            else dp[mask] = i;// memorize the first position
            for(int j=0; j<10; ++j) {// check one letter with odd count
                int t = mask ^ (1<<j);
                if(dp[t] != -2) res = max(res, i - dp[t]);
            }
        }
        return res;
    }
};