Code Implementation

class Solution:
    def longestAwesome(self, s: str) -> int:
        pos = {0: -1}
        mask = 0
        res = 0
        for i, ch in enumerate(s):
            digit = int(ch)
            mask ^= (1 << digit)
            if mask in pos:
                res = max(res, i - pos[mask])
            else:
                pos[mask] = i
            for d in range(10):
                test_mask = mask ^ (1 << d)
                if test_mask in pos:
                    res = max(res, i - pos[test_mask])
        return res
      

class Solution {
public:
    int longestAwesome(string s) {
        unordered_map<int, int> pos;
        pos[0] = -1;
        int mask = 0, res = 0;
        for (int i = 0; i < s.size(); ++i) {
            int digit = s[i] - '0';
            mask ^= (1 << digit);
            if (pos.count(mask))
                res = max(res, i - pos[mask]);
            else
                pos[mask] = i;
            for (int d = 0; d < 10; ++d) {
                int test_mask = mask ^ (1 << d);
                if (pos.count(test_mask))
                    res = max(res, i - pos[test_mask]);
            }
        }
        return res;
    }
};
      

import java.util.*;

class Solution {
    public int longestAwesome(String s) {
        Map<Integer, Integer> pos = new HashMap<>();
        pos.put(0, -1);
        int mask = 0, res = 0;
        for (int i = 0; i < s.length(); ++i) {
            int digit = s.charAt(i) - '0';
            mask ^= (1 << digit);
            if (pos.containsKey(mask))
                res = Math.max(res, i - pos.get(mask));
            else
                pos.put(mask, i);
            for (int d = 0; d < 10; ++d) {
                int testMask = mask ^ (1 << d);
                if (pos.containsKey(testMask))
                    res = Math.max(res, i - pos.get(testMask));
            }
        }
        return res;
    }
}
      

var longestAwesome = function(s) {
    let pos = new Map();
    pos.set(0, -1);
    let mask = 0, res = 0;
    for (let i = 0; i < s.length; ++i) {
        let digit = s.charCodeAt(i) - '0'.charCodeAt(0);
        mask ^= (1 << digit);
        if (pos.has(mask))
            res = Math.max(res, i - pos.get(mask));
        else
            pos.set(mask, i);
        for (let d = 0; d < 10; ++d) {
            let testMask = mask ^ (1 << d);
            if (pos.has(testMask))
                res = Math.max(res, i - pos.get(testMask));
        }
    }
    return res;
};
      

Problem Description

You are given a string s consisting only of digits ('0' to '9'). A substring of s is called awesome if, after rearranging its characters, it becomes a palindrome (reads the same forwards and backwards).

Your task is to find the length of the longest awesome substring in s.

• Each digit may be used as many times as it appears in the substring.
• Substrings are contiguous sequences of characters within s.
• Rearrangement is allowed, so the order of characters in the substring can be changed.
• You must return the length of the longest such substring.

Constraints:

• 1 ≤ s.length ≤ 10⁵
• s consists only of digits ('0' to '9').

Thought Process

The core challenge is to efficiently check, for every substring, whether it can be rearranged into a palindrome.

At first, one might consider checking all possible substrings and, for each, counting digit frequencies to see if at most one digit occurs an odd number of times (which is the necessary and sufficient condition for a string to be rearranged into a palindrome). However, this brute-force approach is too slow for large strings.

To optimize, we need a way to quickly determine, for any substring, if its digit counts meet the palindrome condition. This leads us to use prefix masks (bitmasks) that encode the parity (odd/even) of each digit's count up to each position. If two prefixes have the same mask, the substring between them has all even counts. If they differ by only one bit, the substring has exactly one odd count, which is also allowed for a palindrome.

So, the problem becomes one of finding the farthest pair of indices with matching or single-bit-differing masks, which can be done efficiently with hashing.

Solution Approach

Let's break down the algorithm step by step:

1. Represent the Parity of Digit Counts with a Bitmask:
   • For each position in the string, we keep a 10-bit integer (since there are 10 digits), where the i-th bit is 1 if the count of digit i is odd up to that point, and 0 if even.
2. Prefix Mask and Hash Map:
   • We maintain a hash map (pos) that records the first index where each mask occurs.
   • We initialize the map with mask 0 at index -1, representing an empty prefix.
3. Iterate Over the String:
   • For each character, update the mask by flipping the bit for its digit.
   • If the current mask has been seen before, the substring between the previous position and the current can be rearranged into a palindrome (all digits have even counts).
   • For each digit (0-9), also check if flipping just that digit's bit in the mask yields a mask seen before; this covers the case where only one digit has an odd count.
4. Update the Result:
   • Keep track of the maximum substring length found that meets the palindrome condition.
5. Return the Answer:
   • After iterating through the string, return the maximum length found.

This approach ensures that each mask is processed in constant time, making the solution efficient enough for large input sizes.

Example Walkthrough

Let's use the input s = "3242415" as an example.

1. Start with mask = 0, pos = {0: -1}, res = 0.
2. For each character:
   • i=0, ch='3': mask ^= (1<<3) → mask=8. pos[8] not seen before, so pos[8]=0.
   • i=1, ch='2': mask ^= (1<<2) → mask=12. pos[12] not seen before, so pos[12]=1.
   • i=2, ch='4': mask ^= (1<<4) → mask=28. pos[28] not seen before, so pos[28]=2.
   • i=3, ch='2': mask ^= (1<<2) → mask=24. pos[24] not seen before, so pos[24]=3.
   • i=4, ch='4': mask ^= (1<<4) → mask=8. pos[8]=0 already seen. So, res = max(res, 4-0) = 4.
   • i=5, ch='1': mask ^= (1<<1) → mask=10. pos[10] not seen before, so pos[10]=5.
   • i=6, ch='5': mask ^= (1<<5) → mask=42. pos[42] not seen before, so pos[42]=6.
3. At each step, also check for all masks that differ by one bit (to allow one odd digit count). For i=6, mask=42, flipping bit 1 gives mask=40, which was not seen. Flipping bit 3 gives mask=34, etc. The maximum length found is 5 (for substring "24241").

The output for this example is 5.

Time and Space Complexity

• Brute-force Approach:
  • Checking every substring is O(N²).
  • For each substring, counting digit frequencies is O(N), so total is O(N³).
  • This is not feasible for N up to 10⁵.
• Optimized Approach (Bitmask + Hash Map):
  • We iterate through the string once, O(N).
  • For each character, we do O(1) work (10 checks for single-bit flips).
  • Total time: O(10N) = O(N).
  • Space: O(2¹⁰) for the hash map (since there are only 1024 possible masks), plus O(N) for the string.

Thus, the optimized solution is very efficient and suitable for large inputs.

Summary

To solve the "Find Longest Awesome Substring" problem, we use a bitmask to track the parity of digit counts and a hash map to remember the earliest occurrence of each mask. By checking for matching masks and masks differing by one bit, we can efficiently determine the longest substring that can be rearranged into a palindrome. This approach leverages bit manipulation and prefix properties for a linear time solution, making it both elegant and highly efficient.