Example Input "3242415" Explanation with BitMask
Definition of Awesomeness\nString S is a palindrome if S equals to its reversed version: "1112111"\nAny string is awesome if we can reorder its characters to ma
**Definition of Awesomeness**\nString S is a palindrome if S equals to its reversed version: "1112111"\nAny string is awesome if we can reorder its characters to make it a palindrome: \n"24241" can be reordered to "24142".\n\n**Properties of Awesome string**\nThere are 2 cases that a string can be reordered to be a palindrome:\n**Case 1**. All of its characters have even occurrences: \n\t\t"2424" -> there are two \'2\'s and two \'4\'s.\n**Case 2**. All of its characters have even occurrences except one: \n\t\t"24241" -> there are two \'2\'s, two \'4\'s and one \'1\'\n\t\t\n**Brute force solution**\nThe most straighforward solution would be keeping track of all counters while looping through characters. Once we are at position i, we go back and subtract all our previous counters from our current counter to check if any of them is awesome. However, its time complexity is O(10*N^2): 10 digits * N chars * N comparisons which is not desirable\n\n**BitMask solution**\nWe don\'t have to keep track of counters, we are only interested in odd counts in a substring. We can use one bit to say if some digit has even or odd count at any point.\nLet 0 represent "even" and 1 represent "odd". \nFor example, for an input of "233":\n1. i = 0, char = \'2\', xor 2nd bit from right:\n\tmask = "100"\n2. i = 1, char = \'3\', xor 3rd bit from right:\n\tmask = "1100"\n3. i = 2, char = \'3\', xor 3rd bit from right:\n\tmask = "0100"\n\t\nThe last mask is "0100" which says it has only one number with odd count, so, the input can be rearranged to make it a palindrome: "233" => "323".\n\nEven simpler, if the input is "22", we set and unset 2nd bit, then the remaining mask would be "000", which says we have numbers with all having even counts.\n\nNow, let\'s analyze the example input "3242415" from problem definition.\n1. i = 0, char = \'3\', xor 3rd bit from right:\n\n\t\tmask = \'0000001000\'\n2. i = 1, char = \'2\', xor 2nd bit from right:\n\t\n\t\tmask = \'0000001100\'\n3. i = 2, char = \'4\', xor 4th bit from right:\n    \n\t\tmask = \'0000011100\'\n4. i = 3, char = \'2\', xor 2nd bit from right:\n\t\n\t\tmask = \'0000011000\'\n5. i = 4, char = \'4\', xor 4th bit from right:\n\t\n\t\tmask = \'0000001000\'\n6. i = 5, char = \'1\', xor 1st bit from right:\n\t\n\t\tmask = \'0000001010\'\n7. i = 6, char = \'5\', xor 5th bit from right:\n\t\n\t\tmask = \'0000101010\'\n\t\nThe problem asks to find the longest awesome substring, it can be anywhere between i and j such that i <= j <= lenth of input. For this, on every step above, we need to memoize the current mask and check if we have seen similar mask before.\nUpdate the answer if:\n\t\ta. We have seen similar mask before.\n\t\tb. We have seen a mask such that it differs from the current mask by one bit being different.\n\n```\nclass Solution:\n    def longestAwesome(self, s: str) -> int:\n        n = len(s)\n        ans, mask = 0, 0\n        \n        memo = [n] * 1024\n        memo[0] = -1\n        \n        for i in range(n):\n            mask ^= 1 << int(s[i])\n\t\t\t\n\t\t\t# Case 1. Check if we have seen similar mask\n            ans = max(ans, i - memo[mask])\n            \n\t\t\t# Case 2. Check for masks that differ by one bit\n            for j in range(10):\n                test_mask = mask ^ (1 << j)\n                ans = max(ans, i - memo[test_mask])\n                \n\t\t\t# save the earliest position\n            memo[mask] = min(memo[mask], i)    \n        \n        return ans\n```\nThere are number of questions arise from the above solution:\n**Question 1. Why 1024?**\nSince the input only contains 10 digits ("0123456789"), we can only see 2^10 or 1024 variations of bit masks: 0000000000, 0000000001, .... , 1111111110, 1111111111\n**Question 2. What is 1 << int(s[i])**\nIt shifts 1 by s[i] times, for ex: 1 << 3 gives us \'1000\'.\nAnd it updates the current mask: 0000 ^ 1000 = 1000 or 1110 ^ 1000 = 0110 \nIf you didn\'t get it, please, read bit operations in depth.\n**Question 3. What is the test mask**\nThe test mask in above solution alters one of the bits of the current mask to check for Case 2.\n**Question 4. Why do we check for similar masks?**\nThat means between the similar mask and the current mask, we have seen such digits that xored themselves along the way and disappeared from the mask. Only if the number of digits is even, they can disappear from the current mask: for ex: "223", the current mask evolution is: "100" -> "000" -> "1000". \n**Question 5. Why do we check for masks that differ by one bit?**\nSince it is allowed to have one number with odd count, we can check for masks that differ by one bit from the current mask.\n\nI think, you got this, let me know if you have any other questions.\n
['Bit Manipulation', 'Bitmask']