Find Longest Awesome Substring solution and explanation
9 more videos on this problem
Find Longest Awesome Substring | Leetcode 1542Pepcoding · 34:47 · 5K views
1542. Find Longest Awesome Substring | Leetcode | Biweekly 32Roshan Srivastava · 21:27 · 3K views
花花酱 LeetCode 1542. Find Longest Awesome Substring - 刷题找工作 EP349Hua Hua · 17:29 · 2K views
1542. Find Longest Awesome Substring (Leetcode Hard)Programming Live with Larry · 13:56 · 1K views
[Editorial] Leetcode 1542: Find Longest Awesome Substring (Biweekly Contest 32)Daksh Experiments · 24:40 · 763 views
【每日一题】1542. Find Longest Awesome Substring, 8/10/2020Huifeng Guan · 29:19 · 682 views
Day 40/75: Problem Name: Find Longest Awesome Substring | Leetcode | #75DaysHardLeetcodeCodeInsanity · 9:46 · 522 views
Hashing 3. Find Longest Awesome Substring | AlgoMaster Sheet | Leetcode 1542 |CS FOR ALL · 15:27 · 235 views
[Thinking Out Loud] Leetcode 1542: Find Longest Awesome Substring Part 1/2 (Biweekly Contest 32)Daksh Experiments · 45:37 · 227 views
LeetCode 1542 – Longest Awesome Substring | Bitmask Trick ExplainedCodehurdle · 26:53 · 90 views
The problem
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.
def longestAwesome(s: str) -> int:
n = len(s)
mask = 0
max_length = 0
prefix = {0: -1} # To handle the whole string being a palindrome
for i, char in enumerate(s):
# Compute bitmask
mask ^= 1 << int(char)
if mask in prefix:
max_length = max(max_length, i - prefix[mask])
else:
prefix[mask] = i
# Check for palindromes with one odd digit
for j in range(10):
opt_mask = mask ^ (1 << j)
if opt_mask in prefix:
max_length = max(max_length, i - prefix[opt_mask])
return max_lengthimport java.util.HashMap;
public class Solution {
public int longestAwesome(String s) {
HashMap<Integer, Integer> prefix = new HashMap<>();
prefix.put(0, -1);
int mask = 0;
int maxLength = 0;
for (int i = 0; i < s.length(); i++) {
mask ^= (1 << (s.charAt(i) - '0'));
if (prefix.containsKey(mask)) {
maxLength = Math.max(maxLength, i - prefix.get(mask));
} else {
prefix.put(mask, i);
}
for (int j = 0; j < 10; j++) {
int optMask = mask ^ (1 << j);
if (prefix.containsKey(optMask)) {
maxLength = Math.max(maxLength, i - prefix.get(optMask));
}
}
}
return maxLength;
}
}#include <unordered_map>
#include <string>
using namespace std;
int longestAwesome(string s) {
unordered_map<int, int> prefix;
prefix[0] = -1;
int mask = 0, maxLength = 0;
for (int i = 0; i < s.length(); ++i) {
mask ^= (1 << (s[i] - '0'));
if (prefix.count(mask))
maxLength = max(maxLength, i - prefix[mask]);
else
prefix[mask] = i;
for (int j = 0; j < 10; ++j) {
int optMask = mask ^ (1 << j);
if (prefix.count(optMask))
maxLength = max(maxLength, i - prefix[optMask]);
}
}
return maxLength;
}function longestAwesome(s) {
let prefix = {0: -1};
let mask = 0;
let maxLength = 0;
for (let i = 0; i < s.length; i++) {
mask ^= (1 << (s[i] - '0'));
if (mask in prefix) {
maxLength = Math.max(maxLength, i - prefix[mask]);
} else {
prefix[mask] = i;
}
for (let j = 0; j < 10; j++) {
let optMask = mask ^ (1 << j);
if (optMask in prefix) {
maxLength = Math.max(maxLength, i - prefix[optMask]);
}
}
}
return maxLength;
}#include <string.h>
int longestAwesome(char* s) {
int prefix[1024];
memset(prefix, -1, sizeof(prefix));
prefix[0] = -1;
int mask = 0, maxLength = 0, n = strlen(s);
for (int i = 0; i < n; ++i) {
mask ^= (1 << (s[i] - '0'));
if (prefix[mask] != -1)
maxLength = (maxLength > i - prefix[mask]) ? maxLength : i - prefix[mask];
else
prefix[mask] = i;
for (int j = 0; j < 10; ++j) {
int optMask = mask ^ (1 << j);
if (prefix[optMask] != -1)
maxLength = (maxLength > i - prefix[optMask]) ? maxLength : i - prefix[optMask];
}
}
return maxLength;
}using System;
using System.Collections.Generic;
public class Solution {
public int LongestAwesome(string s) {
Dictionary<int, int> prefix = new Dictionary<int, int>();
prefix[0] = -1;
int mask = 0, maxLength = 0;
for (int i = 0; i < s.Length; i++) {
mask ^= (1 << (s[i] - '0'));
if (prefix.ContainsKey(mask)) {
maxLength = Math.Max(maxLength, i - prefix[mask]);
} else {
prefix[mask] = i;
}
for (int j = 0; j < 10; j++) {
int optMask = mask ^ (1 << j);
if (prefix.ContainsKey(optMask)) {
maxLength = Math.Max(maxLength, i - prefix[optMask]);
}
}
}
return maxLength;
}
}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.
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.
function longestAwesome(s: string): number {
const d: number[] = Array(1024).fill(-1);
let [st, ans] = [0, 1];
d[0] = 0;
for (let i = 1; i <= s.length; ++i) {
const v = s.charCodeAt(i - 1) - '0'.charCodeAt(0);
st ^= 1 << v;
if (d[st] >= 0) {
ans = Math.max(ans, i - d[st]);
} else {
d[st] = i;
}
for (let v = 0; v < 10; ++v) {
if (d[st ^ (1 << v)] >= 0) {
ans = Math.max(ans, i - d[st ^ (1 << v)]);
}
}
}
return ans;
}func longestAwesome(s string) int {
d := [1024]int{}
d[0] = 1
st, ans := 0, 1
for i, c := range s {
i += 2
st ^= 1 << (c - '0')
if d[st] > 0 {
ans = max(ans, i-d[st])
} else {
d[st] = i
}
for v := 0; v < 10; v++ {
if d[st^(1<<v)] > 0 {
ans = max(ans, i-d[st^(1<<v)])
}
}
}
return ans
}Complexity comparison
| Approach | Complexity |
|---|---|
| Prefix and Bitmask Tracking | Time Complexity: O(n), where n is the length of string |
| State Compression + Prefix Sum | – |
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 |
Frequently asked questions
Is Find Longest Awesome Substring easy or hard?
Find Longest Awesome Substring is classified as a Hard problem on LeetCode. The difficulty comes from recognizing that only digit parity matters and encoding it with bitmasks. Once the parity insight is clear, the implementation becomes a clean linear-time scan.
Find Longest Awesome Substring Python/Java solution
Python and Java implementations follow the same logic: maintain a running bitmask for digit parity, store the first index of each mask, and check masks that differ by one bit. The algorithm processes the string once and updates the maximum substring length when matching masks are found.
How to solve Find Longest Awesome Substring in O(n)?
Track the parity of digits using a 10-bit mask while iterating through the string. Store the earliest index where each mask appears. If the same mask appears again, the substring between them has all even frequencies. Also check masks that differ by one bit to allow a single odd digit, enabling palindrome rearrangement.
What is the best approach for Find Longest Awesome Substring?
The best approach uses prefix parity with a 10-bit mask and a hash table. Each bit represents whether a digit has appeared an odd number of times in the prefix. While scanning the string, you store the earliest index of each mask and check masks that differ by one bit. This finds substrings that can form palindromes in O(n) time.
Is Find Longest Awesome Substring asked at Google/Amazon/Meta?
Palindrome substring problems with bitmask parity tricks frequently appear in interviews at companies like Google, Amazon, and Meta. Variants that track odd/even frequency using bit manipulation are especially common in senior-level coding interviews.
What data structure is used in Find Longest Awesome Substring?
The solution primarily uses a hash table (or array) to store the earliest index of each bitmask state. Bit manipulation encodes digit frequency parity into a 10-bit integer, allowing constant-time state comparisons during the string scan.
What is the time complexity of Find Longest Awesome Substring?
The optimal solution runs in O(n * 10) time, which simplifies to O(n). For every character, the algorithm checks the current parity mask and up to 10 masks that differ by one bit. Space complexity is O(1024) because only 2^10 possible digit parity states exist.