#1542

Hard

LeetCode Problem Workspace

Find Longest Awesome Substring

Find the maximum-length awesome substring in a numeric string using hash table and bit manipulation for palindrome potential.

hash table string bit manipulation

Problem Statement

Given a numeric string s, define an awesome substring as a contiguous non-empty segment where characters can be rearranged via swaps to form a palindrome. Your task is to identify such substrings efficiently and return the length of the longest one.

Return the length of the maximum-length awesome substring within s. For example, given s = "3242415", the longest awesome substring is "24241" because it can be rearranged into a palindrome, yielding the result 5.

Examples

Example 1

Input: s = "3242415"

Output: 5

"24241" is the longest awesome substring, we can form the palindrome "24142" with some swaps.

Example 2

Input: s = "12345678"

Output: 1

Example details omitted.

Example 3

Input: s = "213123"

Output: 6

"213123" is the longest awesome substring, we can form the palindrome "231132" with some swaps.

Constraints

1 <= s.length <= 105
s consists only of digits.

Solution Approach

Use a Bitmask to Track Odd Counts

Map each digit to a bit in an integer mask; flipping a bit indicates the digit has an odd count. A substring can form a palindrome if at most one bit is set in the mask.

Hash Table for First Occurrences

Maintain a hash table mapping each mask to its earliest index. For each new position, check if the current mask or masks differing by one bit have been seen to calculate potential awesome substring lengths.

Iterate and Update Maximum Length

Traverse the string once, updating the mask and checking the hash table. Keep a running maximum of valid lengths, ensuring that any palindrome condition is captured immediately for efficiency.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

Time complexity is O(n) because each character is processed once with constant-time mask and hash operations. Space complexity is O(2^10) due to storing first occurrences for all possible 10-bit masks representing digit parities.

What Interviewers Usually Probe

Are you tracking character counts efficiently to evaluate palindrome potential?
Consider using a hash table to avoid redundant substring checks and speed up comparisons.
Think about bitmasking to condense digit parity states and simplify palindrome verification.

Common Pitfalls or Variants

Common pitfalls

Failing to check masks differing by one bit, which allows for a central odd digit in palindromes.
Using nested loops to check all substrings, which leads to timeouts on large inputs.
Not initializing the hash table for mask zero, which misses substrings starting at index 0.

Follow-up variants

Find the number of awesome substrings instead of the longest one, counting all valid segments.
Adapt the problem to alphabetic strings, tracking character counts with a larger bitmask or array.
Find the longest substring forming a k-palindrome, allowing up to k mismatches in the bitmask.

FAQ

What is an awesome substring in this problem?

An awesome substring is a contiguous segment of s where digits can be rearranged via swaps to form a palindrome.

Why use a bitmask instead of counting each digit separately?

A bitmask efficiently encodes the parity of all 10 digits, allowing constant-time palindrome checks for each substring.

How does the hash table improve performance?

It records the earliest index for each bitmask, enabling quick calculation of longest valid substrings without nested loops.

Can this approach handle very large strings up to 10^5 characters?

Yes, the O(n) traversal with constant-time mask operations ensures efficient processing for large inputs.

Which pattern does this problem exemplify for interview prep?

It demonstrates the Hash Table plus String pattern combined with bit manipulation to optimize palindrome substring detection.

terminal

Solution

Solution 1: 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.

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

class Solution:
    def longestAwesome(self, s: str) -> int:
        st = 0
        d = {0: -1}
        ans = 1
        for i, c in enumerate(s):
            v = int(c)
            st ^= 1 << v
            if st in d:
                ans = max(ans, i - d[st])
            else:
                d[st] = i
            for v in range(10):
                if st ^ (1 << v) in d:
                    ans = max(ans, i - d[st ^ (1 << v)])
        return ans

Continue Practicing

#1525 number of good ways to split a string #1461 check if a string contains all binary codes of size k #1684 count the number of consistent strings