Find Longest Awesome Substring - Solution & Explanation
Problem Statement
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 <= 105sconsists only of digits.
Approach Overview
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 1: Prefix and Bitmask Tracking
To solve this problem, we can use a combination of prefix bitmask technique and hash map to keep track of the prefixes. The idea is to use a bitmask to represent the parity (odd/even) of digit counts in the substring. By managing the bitmask, we can determine potentially valid palindrome substrings by checking the parity of digits. A palindrome can have at most one digit with an odd count. Therefore, the bitmask should ideally be all zeros, or it can have only one bit as 1. We'll traverse through the string while adjusting the bitmask, and for each new bitmask, we check if we have seen it before.
The solution iterates through string s while maintaining a bitmask representing parity of counts of digits encountered. The current index is stored in a hashmap at each unique mask found. For each character, the potential palindrome length is calculated by checking previous occurrences of same masks or masks with one bit different.
Complexity
Time Complexity: O(n), where n is the length of string s
Space Complexity: O(1), as we use a fixed-length hashmap and a bitmask.
Approach 2: State Compression + Prefix Sum
According to the problem description, the characters in the "super awesome substring" can be swapped to obtain a palindrome string. Therefore, there is at most one digit character in the "super awesome substring" that appears an odd number of times, and the rest of the digit characters appear an even number of times.
We can use an integer st to represent the parity of the digit characters in the current prefix string, where the i-th bit of st represents the parity of the digit character i, i.e., the i-th bit of st is 1 means that the digit character i appears an odd number of times, and 0 means that the digit character i appears an even number of times.
If the substring s[j,..i] is a "super awesome string", then the state st of the prefix string s[0,..i] and the state st' of the prefix string s[0,..j-1] differ by at most one bit in binary. This is because, if the binary bits are different, it means that the parity is different, and if the parity is different, it means that the number of times the digit appears in the substring s[j,..i] is odd.
So, we can use a hash table or array to record the first occurrence of all states st. If the state st of the current prefix string already exists in the hash table, it means that all bits in the binary of the state st of the current prefix string and the state st' of the prefix string s[0,..j-1] are the same, i.e., the substring s[j,..i] is a "super awesome string", and we update the maximum value of the answer. Or, we can enumerate each bit, flip the i-th bit of the state st of the current prefix string, i.e., st \oplus 2^i, and then check whether st \oplus 2^i is in the hash table. If it is, it means that only the i-th bit in the binary of the state st of the current prefix string and the state st' \oplus 2^i of the prefix string s[0,..j-1] is different, i.e., the substring s[j,..i] is a "super awesome string", and we update the maximum value of the answer.
Finally, return the answer.
The time complexity is O(n times C), and the space complexity is O(2^C). Where n and C are the length of the string s and the number of types of digit characters, respectively.
Code
Python
Java
C++
Go
TypeScript
Complexity Comparison
| Approach | Complexity |
|---|---|
| Prefix and Bitmask Tracking | Time Complexity: O(n), where n is the length of string |
| State Compression + Prefix Sum | — |
Detailed Complexity Analysis
| 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 |
Video Solution
Find Longest Awesome Substring | Leetcode 1542 • Pepcoding • 5,216 views views
Watch 9 more video solutions →Frequently Asked Questions
Is Find Longest Awesome Substring easy or hard?
Find Longest Awesome Substring Python/Java solution
How to solve Find Longest Awesome Substring in O(n)?
What is the best approach for Find Longest Awesome Substring?
Is Find Longest Awesome Substring asked at Google/Amazon/Meta?
What data structure is used in Find Longest Awesome Substring?
What is the time complexity of Find Longest Awesome Substring?
Ready to solve this problem?
Practice Find Longest Awesome Substring with our built-in code editor and test cases.
Practice on FleetCode