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.

Description Hints 3 Solution Video 34:47

1542. Find Longest Awesome Substring

Hard47.4% acceptance1 company

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 <= 10⁵
s consists only of digits.

Asked at 1 company

Directi

Topics

Hints open one at a time

Hint 1

Given the character counts, under what conditions can a palindrome be formed ?

Hint 2

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')).

Hint 3

Expected complexity is O(n*A) where A is the alphabet (10).

34:47

Still stuck?Read 2 approaches, or watch a walkthrough.

Open solution

LanguageLoading editor…

1class Solution:
2    def longestAwesome(self, s: str) -> int:
3        

Starter codePython 3Spaces: 4

Examples

Case 1Case 2Case 3

Input

"3242415"

Input

"12345678"

Input

"213123"

Your code is saved on this device.Solution