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 palindrome.

Return the length of the maximum length awesome substring of s.

Example 1:

Input: s = "3242415"
Output: 5
Explanation: "24241" is the longest awesome substring, we can form the palindrome "24142" with some swaps.


Example 2:

Input: s = "12345678"
Output: 1


Example 3:

Input: s = "213123"
Output: 6
Explanation: "213123" is the longest awesome substring, we can form the palindrome "231132" with some swaps.


Example 4:

Input: s = "00"
Output: 2


Constraints:

• 1 <= s.length <= 10^5
• s consists only of digits.

## Solution: Prefix mask + Hashtable

For a palindrome all digits must occurred even times expect one. We can use a 10 bit mask to track the occurrence of each digit for prefix s[0~i]. 0 is even, 1 is odd.

We use a hashtable to track the first index of each prefix state.
If s[0~i] and s[0~j] have the same state which means every digits in s[i+1~j] occurred even times (zero is also even) and it’s an awesome string. Then (j – (i+1) + 1) = j – i is the length of the palindrome. So far so good.

But we still need to consider the case when there is a digit with odd occurrence. We can enumerate all possible ones from 0 to 9, and temporarily flip the bit of the digit and see whether that state happened before.

fisrt_index[0] = -1, first_index[*] = inf
ans = max(ans, j – first_index[mask])

Time complexity: O(n)
Space complexity: O(2^10) = O(1)

## Python3

If you like my articles / videos, donations are welcome.

Buy anything from Amazon to support our website

Paypal
Venmo
huahualeetcode