✅[cpp || Best Explanation || 🔥TC O(n) || SC O(n)🔥 || 🔥Beats 74.13% and  81.15%🔥]✅
Intuition\n- A palindrome can be of two form or nature :-\n\n 1.  abc-cba every digit or character occurs even number of times.\n\n2. abc-d-cba one digit or cha
# Intuition\n- A palindrome can be of two form or nature :-\n\n 1.  <b>abc-cba</b> every digit or character occurs even number of times.\n\n2. <b>abc-d-cba</b> one digit or character occur odd number of times and rest of the character occurs even number of times.\n- Now instead of finding possible palindromic substring our problem is reduced to finding the substrings that is either of nature 1 or nature 2.\n\n- We can do this by keeping tack of the occurence of the prefix characters or digits (something like a prefix occurrence array).\n\n- After we have our prefix occurrence array we can easily solve this problem using below properties (just like we solve queries using a prefix sum array) :-\n \neven - odd = odd\nodd - odd = even\n\n\n# Approach\n- Essentially we only need to know that upto a point in our string if a character has occurred even or odd number of times.\n- As the characters in our string only varies from \'0\'-\'9\' we can use an integer corresponding to each index to store this data.\n\n|     2    |     3   |    6    |    6    |   4     |    5    |   4   |     5    |     2   |\n| -------- | ------- | ------- | ------- | ------- | ------- |------- | -------  | ------- |\n| 2-odd | 2-odd<br>3-odd | 2-odd<br>3-odd<br>6-odd | 2-odd<br>3-odd<br>6-even   | 2-odd<br>3-odd<br>6-even<br>4-odd |  2-odd<br>3-odd<br>6-even<br>4-odd<br>5-odd | 2-odd<br>3-odd<br>6-even<br>4-even<br>5-odd | 2-odd<br>3-odd<br>6-even<br>4-even<br>5-even | 2-even<br>3-odd<br>6-even<br>4-even<br>5-even |\n| 9876543210<br>0000000100 | 9876543210<br>0000001100 | 9876543210<br>0001001100 | 9876543210<br>0000001100 | 9876543210<br>0000011100 | 9876543210<br>0000111100 | 9876543210<br>0000101100 | 9876543210<br>0000001100 | 9876543210<br>0000001000 |\n\n\n\n# Complexity\n- Time complexity: O(n)\n\n- Space complexity: O(n)\n\n\n\n# Code - 1\n```\nclass Solution {\npublic:\n    int longestAwesome(string s) {\n        unordered_map<int, int> m; //{mask, idx}\n        m[0] = -1;\n\n        int ans = 0;\n        int state = 0;\n        for(int i = 0; i < s.length(); i++) {\n            int mask = (1 << (s[i] - \'0\'));\n            state ^= mask;\n\n            if(m.find(state) != m.end()) {\n                int j = m[state];\n                ans = max(ans, i - j);\n            }\n\n            for(int odd = 0; odd < 10; odd++) {\n                mask = (1 << odd);\n                if(m.find(state ^ mask) != m.end()) {\n                    int j = m[state ^ mask];\n                    ans = max(ans, i - j);\n                }\n            }\n\n            // to maximize length add occurrence mask only once\n            // if we add a occurrence mask twice it will update the key\'s previous value leading to inaccurate result \n            if(m.find(state) == m.end()) {\n                m[state] = i;\n            }\n        }\n\n        return ans;\n    }\n};\n```\n\n# Optimization Intuition\n- As the value of occurence mask can only vary from 1111111111(binary) - 0000000000(binary) . Instead of a map we can create an array of size 10000000000(binary) to store prefix occurrence data.\n- Making out code faster and memory efficient.\n\n\n# Code - 2\n```\nclass Solution {\npublic:\n    int longestAwesome(string s) {\n        vector<int> m(1 << 10, -2); //{mask, idx}\n        m[0] = -1;\n\n        int ans = 0;\n        int state = 0;\n        for(int i = 0; i < s.length(); i++) {\n            int mask = (1 << (s[i] - \'0\'));\n            state ^= mask;\n\n            if(m[state] != -2) {\n                int j = m[state];\n                ans = max(ans, i - j);\n            }\n\n            for(int odd = 0; odd < 10; odd++) {\n                mask = (1 << odd);\n                if(m[state ^ mask] != -2) {\n                    int j = m[state ^ mask];\n                    ans = max(ans, i - j);\n                }\n            }\n\n            // to maximize length update the value at occurrence mask index only once\n            // if we update the vlaue at occurrence mask index more than once it will update the previous value leading to inaccurate result \n            if(m[state] == -2) {\n                m[state] = i;\n            }\n        }\n\n        return ans;\n    }\n};\n```\n# \uD83D\uDC4D Upvote if it helps\n![UPVOTE](https://i.imgur.com/z4D8DqQ.gif)\n\n\n\n\n
['Bit Manipulation', 'C++']