Find Longest Awesome Substring — Problem & Solution
Find Longest Awesome Substring solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A hard problem.
Find Longest Awesome Substring is a hard coding problem on strings, hash table and bit manipulation, asked in Amazon and Directi interviews.
- Difficulty: Hard
- Topics: Strings, Hash Table, Bit Manipulation, Prefix Sum
- Asked at: Amazon, Directi
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
s is a string of decimal digits. A non-empty substring of s is awesome if its digits can be rearranged (any number of swaps) into a palindrome.
Return the length of the longest awesome substring of s.
Example 1
Input: s = "2026"
Output: 3
Explanation: `"202"` is already a palindrome; the whole string has two digits (0 and 6) with an odd count, so it cannot be rearranged into one.
Example 2
Input: s = "12345678"
Output: 1
Explanation: No two equal digits exist, so only single characters work.
Example 3
Input: s = "1221331"
Output: 7
Explanation: Only the digit 1 occurs an odd number of times, e.g. `"1323231"`.
Constraints
1 <= s.length <= 10^5s consists only of digits
Hints for Find Longest Awesome Substring
Hint 1
A multiset of characters can be arranged into a palindrome exactly when at most one character has an odd count.
Hint 2
Only the parity of each digit's count matters — ten bits. Compute the parity mask of every prefix.
Hint 3
The substring between prefixes
iandjhas parity maskmask[i] XOR mask[j]; it is awesome if that XOR is 0 or a single bit. Store the first index each mask occurs and, at every position, look up the current mask and its ten one-bit neighbours.
How to solve Find Longest Awesome Substring
Encode the odd/even count of each digit in a 10-bit prefix mask. A substring is awesome when the masks at its two ends differ in at most one bit, so remembering where each mask first appeared answers each position in eleven lookups.
Approach
- Keep
first[mask], the earliest prefix length with that parity mask; setfirst[0] = 0(the empty prefix) and mark the other 1,023 as unseen. - Walk the string; after reading digit
dat positionj(1-based prefix lengthj), flip bitdofmask. - If
maskwas seen before, the substring between is all-even: update the answer withj - first[mask]. - For each digit
b, ifmask ^ (1 << b)was seen, that substring has exactly one odd digit: update withj - first[mask ^ (1 << b)]. - If
maskis new, recordfirst[mask] = j. Return the best length.
Why it works
The count of digit d in s[i..j) is the difference of two prefix counts, so its parity is the XOR of the two prefix parities; the substring's parity mask is therefore mask[i] ^ mask[j]. A palindrome arrangement exists iff that mask has at most one set bit. For a fixed right end the longest such substring uses the earliest compatible left prefix, which is exactly what first stores.
Complexity
- Time —
O(10 · n) - Space —
O(2^10)
Pitfalls
- Recording a mask's index again when it reappears loses the earliest position — only set
firstthe first time. - Forgetting the empty prefix (
first[0] = 0) misses awesome substrings that start at index 0. - Checking only the all-even case misses the palindromes with one odd centre digit.
Reference solution
Python
def longestAwesome(s: str) -> int:
first = [-1] * 1024
first[0] = 0
mask = 0
best = 0
for j, ch in enumerate(s, 1):
mask ^= 1 << (ord(ch) - 48)
if first[mask] >= 0:
best = max(best, j - first[mask])
for b in range(10):
m = mask ^ (1 << b)
if first[m] >= 0 and j - first[m] > best:
best = j - first[m]
if first[mask] < 0:
first[mask] = j
return bestJava
public static int longestAwesome(String s) {
int[] first = new int[1024];
Arrays.fill(first, -1);
first[0] = 0;
int mask = 0, best = 0;
for (int j = 1; j <= s.length(); j++) {
mask ^= 1 << (s.charAt(j - 1) - '0');
if (first[mask] >= 0) best = Math.max(best, j - first[mask]);
for (int b = 0; b < 10; b++) {
int m = mask ^ (1 << b);
if (first[m] >= 0 && j - first[m] > best) best = j - first[m];
}
if (first[mask] < 0) first[mask] = j;
}
return best;
}C++
int longestAwesome(string s) {
vector<int> first(1024, -1);
first[0] = 0;
int mask = 0, best = 0;
for (int j = 1; j <= (int)s.size(); j++) {
mask ^= 1 << (s[j - 1] - '0');
if (first[mask] >= 0) best = max(best, j - first[mask]);
for (int b = 0; b < 10; b++) {
int m = mask ^ (1 << b);
if (first[m] >= 0 && j - first[m] > best) best = j - first[m];
}
if (first[mask] < 0) first[mask] = j;
}
return best;
}JavaScript
var longestAwesome = function(s) {
var first = new Array(1024).fill(-1);
first[0] = 0;
var mask = 0, best = 0;
for (var j = 1; j <= s.length; j++) {
mask ^= 1 << (s.charCodeAt(j - 1) - 48);
if (first[mask] >= 0) best = Math.max(best, j - first[mask]);
for (var b = 0; b < 10; b++) {
var m = mask ^ (1 << b);
if (first[m] >= 0 && j - first[m] > best) best = j - first[m];
}
if (first[mask] < 0) first[mask] = j;
}
return best;
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 515 strings problems · the whole catalogue
Learn the technique: Strings · Hashing: Hash Maps and Hash Sets