Bit Masking - C++ Solution Beats 100%
Intuition\n\nHere we will use the bitmask method. Since we have numbers from 0 to 9 , we will create a bitmask with 10 bits. Now the bits will indicate if the f
# Intuition\n\nHere we will use the bitmask method. Since we have numbers from 0 to 9 , we will create a bitmask with 10 bits. Now the bits will indicate if the frequency of that digit is even or odd , 0 means even 1 means odd here. Now if two substrings have same mask, it means all the elements between them can form a palindrome.\nFor example - we have 2 2 2 3 2 2, here the substring 2 2 2 3 have a mask as 1100 and substring 2 2 2 3  2 2 have a bit mast of 1100 as well hence all the elements from 3  to 2 i.e 3 2 2 can form a palindrome. \n\nNow we will keep track of all the masks, we will allow the same masks or the masks where only 1 bit differs as for palindrome either every element have even freq or atmax one element have odd frequency.\n\nwe will subtract the last found mask index from current index, and update the answer. And then update the current mask with the smallest index it was found at.\n\n# Approach\n\ninitialise a arr of size 1024 and values n to keep track of mask. arr[0] = -1 indicating if mask is 0 then all the elements can form palindrome till this index. \n\nfor iterate over the string and toggle the current bit according to the character we found.\n\nLook into the arr if this mask was available before and update the answer accordingly.\n\nNow check for all the masks where only one bit is different and update the answer to max value between ans and i-arr[mask];\n\nAt the end update the current masks index to the lowest index it was found. arr[mask] indicates its previous value , if it was not found before its default value is n , and i is the current index , indicating it is found for the first time here.\n\n# Complexity\n- Time complexity:\n $$O(n)$$\n\n- Space complexity:\n$$O(n)$$\n\n# Code\n```cpp []\nclass Solution {\npublic:\n    int longestAwesome(string s) {\n        int mask = 0;  int n = s.size(); int ans = 0;\n        vector<int>arr(1024,n);\n        arr[0] = -1;\n\n        for(int i = 0; i<n; i++){\n            mask = mask ^ (1 << (s[i]-\'0\'));\n            ans = max(ans , i - arr[mask]);\n\n            for(int j = 0; j<10; j++){\n                int temp = mask^(1<<j);\n                ans = max(ans , i- arr[temp]);\n            }\n\n            arr[mask]=  min(arr[mask] , i);\n        }\n        return ans;\n    }\n};\n```
['C++']