Problem Description
You are given a string s. An awesome substring is a non-empty substring of s such that we can make any number of swaps in order to make it a palindrome. Return the length of the maximum length awesome substring of s.
Key Insights
- A palindrome can have at most one character with an odd count.
- The problem can be reduced to counting the frequency of digits and checking the parity of these counts.
- Using bit manipulation, we can represent the frequency of digits in a bitmask.
- The longest awesome substring can be found by maintaining a hashmap of previously seen bitmask states.
Space and Time Complexity
Time Complexity: O(n)
Space Complexity: O(1) (for the bitmask) + O(n) (for the hashmap)
Solution
To solve the problem, we utilize a bitmask to represent the count of digits from '0' to '9'. Each digit's parity (even or odd) can be represented as a bit in an integer. We iterate through the string while updating the bitmask for each character. We also maintain a hashmap to store the first occurrence of each bitmask. When we encounter a bitmask that has been seen before, we calculate the length of the substring between the first occurrence and the current index. Additionally, we check for bitmasks that differ by one bit (indicating that one character can be odd) to account for potential awesome substrings.