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.The key observation for Find Longest Awesome Substring is that a substring is considered "awesome" if its digits can be rearranged into a palindrome. A palindrome allows at most one character with an odd frequency. Since the string only contains digits 0-9, we can track the parity (even/odd count) of each digit using a bitmask of length 10.
While iterating through the string, maintain a running mask where each bit represents whether a digit count is currently odd. Use a hash table to store the earliest index where each mask appears. For each position, check two cases: the same mask (all digits even) and masks that differ by exactly one bit (one odd digit allowed). These checks help identify the longest valid substring ending at the current index.
This technique efficiently reduces the problem to prefix-state comparison using bit manipulation. The overall time complexity becomes O(n * 10), while the space complexity is limited by the number of possible masks.
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| Prefix Bitmask + Hash Table | O(n * 10) | O(2^10) |
NeetCode
Use these hints if you're stuck. Try solving on your own first.
Given the character counts, under what conditions can a palindrome be formed ?
From left to right, use bitwise xor-operation to compute for any prefix the number of times modulo 2 of each digit. (mask ^= (1<<(s[i]-'0')).
Expected complexity is O(n*A) where A is the alphabet (10).
Watch expert explanations and walkthroughs
Practice problems asked by these companies to ace your technical interviews.
Explore More ProblemsJot down your thoughts, approach, and key learnings
Yes, this problem reflects common interview themes such as prefix states, bitmasking, and hash maps. Variants of this problem frequently appear in technical interviews at top tech companies.
A hash table (or array) is commonly used to store the first occurrence of each bitmask state. This allows constant-time lookups when determining the longest substring with the required parity conditions.
Bit manipulation is used to track whether each digit appears an even or odd number of times. A 10-bit mask represents digits 0–9, allowing fast state comparison and efficient checks for palindrome-permutable substrings.
The optimal approach uses prefix bitmasks with a hash table to track the parity of digit counts. By storing the earliest index of each mask and checking masks that differ by one bit, we can efficiently find the longest valid substring.