Watch 10 video solutions for Find Longest Awesome Substring, a hard level problem involving Hash Table, String, Bit Manipulation. This walkthrough by Pepcoding has 5,130 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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.
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.
Constraints:
1 <= s.length <= 105s consists only of digits.Problem Overview: You are given a numeric string. The task is to find the length of the longest substring that can be rearranged into a palindrome. A string can form a palindrome if at most one character appears an odd number of times. The challenge is detecting such substrings efficiently.
Approach 1: Brute Force Frequency Check (O(n² * 10) time, O(1) space)
The straightforward approach checks every possible substring. For each start index, extend the substring one character at a time and maintain digit frequencies. After each extension, verify whether the substring can be rearranged into a palindrome by counting how many digits have odd frequency. If the count is ≤ 1, update the maximum length. Since the string contains only digits (0–9), the frequency array size stays constant. However, checking every substring leads to O(n²) substrings, making this too slow for large inputs.
Approach 2: Prefix Parity + Bitmask Tracking (O(n * 10) time, O(1024) space)
The optimal solution tracks the parity (odd/even) of each digit using a 10-bit mask. Bit i represents whether digit i has appeared an odd number of times in the current prefix. As you iterate through the string, toggle the corresponding bit with XOR. If two prefixes share the same mask, the substring between them has all digits with even counts and can form a palindrome.
To allow one odd character, check masks that differ by exactly one bit. For each index, compute the current mask and check if it already appeared earlier. Also flip each of the 10 bits and check those masks in a hash map storing the earliest index where each mask appeared. This efficiently detects substrings where at most one digit has odd frequency.
This technique combines prefix state tracking with constant-size parity representation. The mask range is only 2^10, so memory stays small. The approach relies heavily on bit manipulation to represent parity states and a hash table to track the earliest index of each mask while scanning the string.
Recommended for interviews: The prefix bitmask solution is what interviewers expect. Brute force demonstrates the key palindrome insight (at most one odd frequency), but the bitmask technique shows stronger algorithmic skill and reduces the runtime to near linear. Recognizing that only parity matters—and compressing it into a 10-bit integer—is the critical optimization.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force Frequency Check | O(n² * 10) | O(1) | Useful for understanding the palindrome condition and verifying logic on small inputs |
| Prefix Parity Bitmask + Hash Map | O(n * 10) | O(1024) | Optimal approach for interviews and large inputs; tracks digit parity efficiently |