LeetCode 1542 - Find Longest Awesome Substring

The problem asks us to find the length of the longest awesome substring in a given string s consisting of digits. A subs

leetcodehardhash-tablestringbit-manipulation

LeetCode Problem 1542

Difficulty: 🔴 Hard
Topics: Hash Table, String, Bit Manipulation

Solution

Problem Understanding

The problem asks us to find the length of the longest awesome substring in a given string s consisting of digits. A substring is considered awesome if it can be rearranged (via any number of swaps) to form a palindrome. In other words, the characters in the substring can be permuted so that it reads the same forwards and backwards.

The input s is a string of length up to 10^5, consisting only of digits from '0' to '9'. The output is an integer representing the maximum length of a substring of s that can be rearranged into a palindrome.

A key property of palindromes is that at most one character can appear an odd number of times, while all other characters must appear an even number of times. This insight will be crucial for designing an efficient solution.

Important edge cases include strings where all characters are unique, strings that are already palindromes, strings of length 1, and strings with repeated characters scattered throughout.

Approaches

The naive approach is to examine every possible substring, count the frequency of each digit, and check if the substring can form a palindrome. This involves generating all substrings of s and checking the palindrome condition for each one.

While correct, this approach is too slow for the constraints since there are O(n^2) substrings, and checking each substring can take up to O(10) for counting digits. This results in O(n^2) time complexity, which is infeasible for n up to 10^5.

The key insight for an optimal solution is bit manipulation. We can represent the parity (odd or even count) of each digit using a 10-bit integer. Each bit corresponds to a digit '0' through '9', and a bit is set if the count of that digit is odd. Using this representation, a substring can form a palindrome if its bitmask has at most one bit set. By tracking the first occurrence of each bitmask, we can calculate the length of the longest awesome substring in linear time.

Approach Time Complexity Space Complexity Notes
Brute Force O(n^2) O(1) Check all substrings, count digit frequencies, verify palindrome condition
Optimal O(n) O(2^10) Use bitmask to track odd/even counts, leverage prefix masks to detect valid substrings

Algorithm Walkthrough

  1. Initialize a dictionary mask_to_index to store the first index where each mask appears. Set mask_to_index[0] = -1 to handle substrings starting at index 0.
  2. Initialize mask = 0 to represent the current parity of digit counts and max_length = 0 to track the result.
  3. Iterate through each character c in the string s using its index i.
  4. Convert the character to an integer digit = int(c).
  5. Update the mask using XOR: mask ^= (1 << digit). This toggles the bit corresponding to the digit, effectively updating the parity.
  6. If the mask has been seen before in mask_to_index, update max_length = max(max_length, i - mask_to_index[mask]). This means the substring between the previous index and the current index can form a palindrome.
  7. To account for a substring with at most one odd-count digit, iterate j from 0 to 9 and check mask ^ (1 << j) in mask_to_index. Update max_length similarly if found.
  8. If the mask has not been seen before, store the current index: mask_to_index[mask] = i.
  9. After processing all characters, return max_length.

Why it works: The bitmask captures the parity of digit counts. Two substrings with the same mask mean the digits in between have even counts (or only one odd), satisfying the palindrome condition. XOR allows us to efficiently compute masks and compare them.

Python Solution

class Solution:
    def longestAwesome(self, s: str) -> int:
        mask_to_index = {0: -1}
        mask = 0
        max_length = 0
        
        for i, c in enumerate(s):
            digit = int(c)
            mask ^= (1 << digit)
            
            if mask in mask_to_index:
                max_length = max(max_length, i - mask_to_index[mask])
            
            for j in range(10):
                test_mask = mask ^ (1 << j)
                if test_mask in mask_to_index:
                    max_length = max(max_length, i - mask_to_index[test_mask])
            
            if mask not in mask_to_index:
                mask_to_index[mask] = i
        
        return max_length

This Python implementation follows the algorithm precisely. mask_to_index tracks first occurrences of each parity mask. The XOR operation toggles the bit corresponding to the current digit. Checking mask and mask ^ (1 << j) efficiently finds substrings that can be rearranged into a palindrome.

Go Solution

func longestAwesome(s string) int {
    maskToIndex := make(map[int]int)
    maskToIndex[0] = -1
    mask := 0
    maxLength := 0

    for i, c := range s {
        digit := int(c - '0')
        mask ^= 1 << digit

        if prev, ok := maskToIndex[mask]; ok {
            if i - prev > maxLength {
                maxLength = i - prev
            }
        }

        for j := 0; j < 10; j++ {
            testMask := mask ^ (1 << j)
            if prev, ok := maskToIndex[testMask]; ok {
                if i - prev > maxLength {
                    maxLength = i - prev
                }
            }
        }

        if _, ok := maskToIndex[mask]; !ok {
            maskToIndex[mask] = i
        }
    }

    return maxLength
}

In Go, the implementation is similar. The key differences are the use of map[int]int for maskToIndex, explicit type conversion for digits, and idiomatic ok checks for map existence.

Worked Examples

Example 1: s = "3242415"

i c mask (binary) mask_to_index max_length
0 '3' 1000 {0:-1} 0
1 '2' 1100 {0:-1} 0
2 '4' 10100 {0:-1} 0
3 '2' 10000 {0:-1} 2 (from mask 1100 → index 1)
4 '4' 0 {0:-1} 5 (from mask 0 → index -1)
5 '1' 10 ... 5
6 '5' 100010 ... 5

Result: 5

Example 2: s = "12345678"

All digits unique, maximum substring of length 1 forms palindrome. Result: 1

Example 3: s = "213123"

Full string forms palindrome after swaps. Result: 6

Complexity Analysis

Measure Complexity Explanation
Time O(n) Iterate through each character once; for each character, check up to 10 variations of the mask
Space O(2^10) Store first occurrence of each 10-bit mask (maximum 1024 entries)

This solution is efficient for the input size (n ≤ 10^5) because the inner loop runs a constant 10 times, and the map size is bounded by 1024.

Test Cases

# Provided examples
assert Solution().longestAwesome("3242415") == 5  # palindrome "24241"
assert Solution().longestAwesome("12345678") == 1  # all unique digits
assert Solution().longestAwesome("213123") == 6  # full string palindrome

# Edge cases
assert Solution().longestAwesome("1") == 1  # single character
assert Solution().longestAwesome("11") == 2  # already a palindrome
assert Solution().longestAwesome("121") == 3  # odd-length palindrome
assert Solution().longestAwesome("112233") == 6  # all counts even
assert Solution().longestAwesome("111222333444555666777888999000") == 30  # all counts multiples of 3
assert Solution().longestAwesome("9876543210") == 1  # no repeated digits
Test Why
"3242415" Validates general palindrome-forming substring
"12345678" Checks handling when no substring >1 is awesome
"213123" Checks full string awesome case
"1" Minimal length edge case
"11" Already a palindrome
"121" Odd-length palindrome
"112233" Multiple even counts
"9876543210" No repeated digits

Edge Cases

Single character strings: A single character is always awesome since a one-character string is trivially a palindrome. The algorithm correctly handles this