Find Longest Awesome Substring

Find Longest Awesome Substring

What is this problem about?

In the Find Longest Awesome Substring coding problem, a string is considered "awesome" if its characters can be rearranged to form a palindrome. You are given a string of digits and need to find the length of the longest awesome contiguous substring. A string can form a palindrome if at most one character appears an odd number of times.

Why is this asked in interviews?

Google uses this "Hard" problem to test a candidate's ability to combine Bit Manipulation with the Prefix Sum interview pattern. It evaluations whether you can represent the state of character parities using a bitmask and use a Hash Table to find the earliest occurrence of a state. It’s a highly efficient $O(n imes 10)$ solution to a problem that initially looks like it requires $O(n^2)$ checks.

Algorithmic pattern used

This problem uses Bitmasking and Prefix Parity.

1. Represent the parity of the counts of digits 0-9 using a 10-bit mask. A bit is 1 if the count is odd, and 0 if even.
2. Initialize a map firstSeen with mask 0 at index -1.
3. Iterate through the string, updating the currentMask using XOR for each digit.
4. Two conditions make a substring from firstSeen[prevMask] to current awesome:
   • Perfect Palindrome: currentMask == prevMask (all characters appear even times).
   • One-odd Palindrome: currentMask ^ prevMask has exactly one bit set (one character appears odd times). Check this by XORing the currentMask with each of the 10 possible single-bit masks.
5. Maximize the length i - firstSeen[targetMask].

Example explanation

String: "324241"

1. mask 0 at -1.
2. '3': mask becomes 0000001000. firstSeen[mask] = 0.
3. '2': mask becomes 0000001100. firstSeen[mask] = 1.
4. '4': ...
5. When another '2' arrives, the bit for '2' flips back. The mask might match a previous state or a state with one bit difference.

Common mistakes candidates make

• $O(n^2)$ approach: Checking all substrings, which fails the time limit.
• Only checking perfect matches: Forgetting that palindromes can have one character with an odd count.
• Initialization: Failing to put the initial state (mask 0) at index -1, which misses valid substrings starting at index 0.

Interview preparation tip

Bitmasks are the standard way to track "parity" for a small number of categories (like 10 digits or 26 letters). Combining this with a Hash Map to store the "first appearance" of each mask is a recurring pattern for "Longest Subarray with Parity Condition" problems.