Bit Masking and Prefix Sum || C++
Intuition\nWe know a string can only become a palindrome in 2 cases :-\n1. If all the distinct elements occurs even no. of times.\n2. If all the distinct elemen
# Intuition\nWe know a string can only become a palindrome in 2 cases :-\n1. If all the distinct elements occurs even no. of times.\n2. If all the distinct elements except one occurs even no. of times.\n\nWe have to find the longest substring that satistfies any one of the above condition.\n\n# Approach\nWe will check for each index if the string ending at it can become palindrome (i.e satisifies above condtion).\nIf it doesn\'t then we will check if removing a substring from its behind helps it become palindrome.\n\nSince the elements present are all digits `(0 - 9)`, we will create bitmask for each index and store them in a prefix array.\nEach index in the bitmask represents corresponding digit.\n\n`0` bit represents that digit at that index have occured even no. of times, `1` represents odd no. of times.\n\nAfter forming the prefix array, we will traverse the string along with maintaining a hashmap to store previously seen bitmask.\n\nfor each index i, \n**if** \nmask == 0 (means all no.s occur even no. of times) \nor mask contains only one 1 i.e it\'s a power of 2 (means all no.s except 1 occurs even no. of times),\nthen we will calculate length of string\n\n**else** \nwe will check if there exists a mask before, xoring with which we get 0\n\ncurMask ^ toBeFindMask = 0\ntoBeFindMask = 0 ^ curMask\ntoBeFindMask = curMask\n\nor we will check if there exists a mask before, xoring with which we get a no. which contains only one 1.\n\ncurMask ^ toBeFindMask = $$2^x$$  (0 <= x <= 9)\ntoBeFindMask = $$2^x$$ ^ curMask\n\nand update max length string found.\n\nStore the bit mask only if it is not seen already, that way we can get the farthest index from current index when we search for it, thereby getting maximum length \n\n\n# Complexity\n- Time complexity: $$O(10*n)$$\n\n- Space complexity: $$O(n)$$\n\n# Code\n```\nclass Solution {\npublic:\n    int longestAwesome(string s) {\n        int n = s.size();\n        vector<int> prefix(n+1);\n        for(int i=0; i<n; i++){\n            int bit = s[i] - \'0\';\n            prefix[i+1] = prefix[i] ^ (1 << bit);\n        }\n\n        unordered_map<int,int> mp;\n        int ans = 0;\n        for(int i=0; i<n; i++){\n            int mask = prefix[i+1];\n            \n            // mask == 0 means all numbers present even times\n            // mask with all 0 except 1 means all numbers present even times except one\n            if(mask == 0 || !(mask & (mask-1))){\n                ans = max(ans, i+1);\n            }\n            else{\n                // check if a mask exist with which if we take XOR we\'ll get a 0\n                // that means check if same mask exist previously\n                if(mp.count(mask)){\n                    ans = max(ans, i-mp[mask]);\n                }\n                // check if a mask exist with which if we take XOR we\'ll get a number which have only one 1\n                for(int j=0; j<10; j++){\n                    int submask = (1 << j);\n                    int f = mask ^ submask;\n                    \n                    if(mp.count(f)){\n                        ans = max(ans, i - mp[f]);\n                    }\n                }\n            }\n            if(!mp.count(mask)){\n                mp[mask] = i;\n            }\n        }\n        return ans;\n    }\n};\n```
['Hash Table', 'Bit Manipulation', 'Prefix Sum', 'C++']