Intuitive Bit Mask solution with Comments
Intuition\nWant to use a bitmask to subsitute a dictionary because our alphabet is a fixed length (the numebr of digits "0-9" = 10 digits). Similar to Prefix Su
# Intuition\nWant to use a bitmask to subsitute a dictionary because our alphabet is a fixed length (the numebr of digits "0-9" = 10 digits). Similar to Prefix Sum + Hashmap Medium problems, but with a bitmask spin to get lower time and space complexity. \n\n# Approach\nRead in-text comments\n\n# Complexity\n- Time complexity:\nO(N) for the outer for loop and O(10) for inner for loop = O(10 * N) = O(N)\n\n- Space complexity:\nO(1), because of bitmask\n\n# Code\n```\nclass Solution {\n    public int longestAwesome(String s) {\n        int ans = 0;\n        // Mask = 0b0000000000 -> There are 10 zeroes because we have 10 possible vals 0-9 as our alphabet\n        // 0th place is 1 if we have odd number of 0s and 0 if we have even number of 0s\n        // 1th place is 1 ... \n        int mask = 0;\n\n        HashMap<Integer, Integer> map = new HashMap();\n        map.put(0, -1);\n\n        for (int idx = 0; idx < s.length(); idx++) {\n            // lets say s.charAt(idx) == 3. We shift 0b1 by 3 so that we get 0b1000\n            // lets say mask = 0b1000 -> the xOr will evaluate to 0b000\n            // This means we had an odd number of 3s now we have an even number of all values\n            mask ^= 1 << (s.charAt(idx) - \'0\');\n\n\n            // If we see matching masks then that means the number of odd characters \n            // and those corresponding characters that are odd are the same\n            // Substracting one substring from another we get a new susbtring with no odd freq characters\n            if (map.containsKey(mask)) {\n                ans = Math.max(ans, idx - map.get(mask));\n            } else {\n                map.put(mask, idx);\n            }\n\n            // Palindrome can also have 1 character with an odd freq (in the middle)\n            for (int shift = 0; shift < 10; shift++) {\n                // Consider all masks that differ by mask in 1 place\n                int oddMask = mask ^ (1 << shift);\n\n                if (map.containsKey(oddMask)) {\n                    ans = Math.max(ans, idx - map.get(oddMask));\n                }\n            }\n        }\n\n        return ans;\n    }\n}\n```
['Java']