Description

Submission

class Solution {
public:
    int longestAwesome(string s) {
        int n = s.length();
        vector<int> pos(1 << 10, -2);
        int state = 0;
        pos[state] = -1;

        int ret = 1;
        for(int i = 0; i < n; ++i) {
            int idx = s[i] - '0';
            state = state ^ (1 << idx);

            for(int k = 0; k < 10; ++k) {
                int newState = state ^ (1 << k);
                if(pos[newState] == -2) {
                    continue;
                }
                
                ret = max(ret, i - pos[newState]);
            }

            if(pos[state] == -2) {
                pos[state] = i;
            } else {
                ret = max(ret, i - pos[state]);
            }
        }

        return ret;
    }
};

// X X X X X X i[X X X X X j] X X X X X X
// for the all even case
// presum['1'][i] % 2
// presum['2'][i] % 2
// .
// presum['9'][i] % 2

// should all be congruent with the 

// presum['1'][j] % 2
// presum['2'][j] % 2
// .
// presum['9'][j] % 2