C++/Python, prefix + mask solution with explanation
To form a palindrome,\nthere have 1 letter with odd occurence, others with even occurence,\nor all letters with even occurence.\n\nWe can use a bitmask to indic
To form a palindrome,\nthere have 1 letter with odd occurence, others with even occurence,\nor all letters with even occurence.\n\nWe can use a bitmask to indicate odd/even occurence.\nAnd use xor operation to check if there has palindrome or not.\nwhy use xor?\nodd - odd = even\neven - even = even\nodd - even = odd\neven - odd = odd\nwhere odd is a bit of 1, even is a bit of 0.\nsuppose prefix mask is x,\nx ^ ? = pow of 2 (1 odd),\n? = x ^ pow of 2.\nx ^ ? = 0 (all even),\n? = x.\n\nuse hash map or array to record index of prefix mask where prefix mask first appear.\n\ntc is O(n), sc is O(1024)\n### python\n```python\nclass Solution:\n    def longestAwesome(self, s: str) -> int:\n        masks = [-2] * 1024\n        masks[0] = -1\n        cur = 0\n        ans = 1\n        for i, x in enumerate(s):\n            cur ^= 1 << int(x)\n            if masks[cur] != -2: ans = max(ans, i - masks[cur])\n            for j in range(10):\n                if masks[cur ^ (1 << j)] != -2: ans = max(ans, i - masks[cur ^ (1 << j)])\n            if masks[cur] == -2: masks[cur] = i\n        return ans\n```\n\n### c++\n```cpp\nclass Solution {\npublic:\n    int longestAwesome(string s) {\n        vector<int> masks (1024, -2);\n        masks[0] = -1;\n        int cur = 0, ans = 1;\n        for (int i = 0; i < s.size(); i+=1) {\n            cur ^= 1 << (s[i] - \'0\');\n            if (masks[cur] != -2) ans = max(ans, i - masks[cur]);\n            for (int j = 0; j < 10; j+=1)\n                if (masks[cur ^ (1 << j)] != -2)\n                    ans = max(ans, i - masks[cur ^ (1 << j)]);\n            if (masks[cur] == -2) masks[cur] = i;\n        }\n        return ans;\n    }\n};\n```
['C', 'Bitmask', 'Python']