C++ solution Masking Technique explained
Intuition\n Describe your first thoughts on how to solve this problem. \nFrom the problem statement, it is clear that we have to find the longest substring in t
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nFrom the problem statement, it is clear that we have to find the longest substring in the given string which has even number of occurrences for each digit from 0 to 9. To accomplish this, we can use a bit masking technique to track the occurrence of each digit in the current substring. \n# Approach\n<!-- Describe your approach to solving the problem. -->\nTo solve this problem, we can use a bit masking technique to track the occurrence of each digit in the current substring. We use a bit mask of length 10 with each bit representing the occurrence of a digit in the current substring. Initially, all the bits in the mask are set to 0. We traverse through the string and everytime we encounter a digit we toggle the corresponding bit in the mask. We also maintain an array pos of length 1024 which stores the index of the last occurence of each mask. We also maintain a variable mask which stores the current bit mask. \n\nWe use the variable res to store the length of the longest awesome substring. For every index, we update the res variable by taking the maximum of the current index minus the last index corresponding to the current mask and current index minus the last index corresponding to the current mask with all its bits toggled. \n# Complexity\n- Time complexity: $$O(n)$$\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity: $$O(n)$$\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```\nclass Solution {\npublic:\n    int longestAwesome(string s) {\n        int res = 0, n = s.size();\n        vector<int> pos(1 << 10, n); // pos array of length 1024 to store the last index of each mask\n        pos[0] = -1; // initially setting the last index corresponding to 0 mask to -1\n        int mask = 0;\n        for (int i = 0; i < n; ++i) {\n            mask ^= 1 << (s[i] - \'0\'); // toggling the bit corresponding to the current digit\n            res = max(res, i - pos[mask]); // updating the res variable with the current index minus the last index corresponding to the current mask\n            for (int j = 0; j < 10; ++j) \n                res = max(res, i - pos[mask ^ (1 << j)]); // updating the res variable with the current index minus the last index corresponding to the current mask with all its bits toggled\n            pos[mask] = min(pos[mask], i); // updating the last index corresponding to the current mask\n        }\n        return res;\n    }\n};\n```
['Hash Table', 'String', 'Bit Manipulation', 'C++']