# Find Longest Awesome Substring
**Difficulty:** HARD
[External](https://leetcode.com/problems/find-longest-awesome-substring)
Canonical: https://scaleengineer.com/dsa/problems/find-longest-awesome-substring
**Patterns:** [Bit Manipulation](https://scaleengineer.com/dsa/patterns/bit-manipulation)
**Data structures:** Hash Table, String
**Companies:** [Directi](https://scaleengineer.com/companies/directi)
---
## Problem
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 <= 105`
* `s` consists only of digits.

# Approaches
## Brute Force Approach
This approach is the most straightforward and involves a brute-force check of every possible substring. For each substring, we perform a full count of its character frequencies to determine if it can be rearranged into a palindrome. A string can be rearranged into a palindrome if at most one of its characters appears an odd number of times.
**Time:** O(N^3), where N is the length of the string `s`. There are O(N^2) substrings, and checking each substring of length L involves an O(L) scan. Since L can be up to N, the total complexity is cubic. · **Space:** O(1), as the frequency map for digits '0'-'9' requires a constant amount of space (an array of size 10).
**Pros:** Simple to understand and implement.; Correctly solves the problem for small input sizes.
**Cons:** Extremely inefficient due to its cubic time complexity.; Will not pass the time limits for the given constraints (N up to 10^5).
### Explanation
The algorithm iterates through all possible start and end points of a substring. For each substring generated, it calculates the frequency of each digit ('0'-'9'). Then, it counts how many of these digits have an odd frequency. If this count is less than or equal to one, the substring is deemed 'awesome', and we update our maximum length found so far. This process is repeated for all O(N^2) substrings.

```java
class Solution {
    public int longestAwesome(String s) {
        int n = s.length();
        int maxLength = 0;
        if (n == 0) return 0;

        for (int i = 0; i < n; i++) {
            for (int j = i; j < n; j++) {
                // Substring s[i..j]
                int[] freq = new int[10];
                for (int k = i; k <= j; k++) {
                    freq[s.charAt(k) - '0']++;
                }

                int oddCount = 0;
                for (int count : freq) {
                    if (count % 2 != 0) {
                        oddCount++;
                    }
                }

                if (oddCount <= 1) {
                    maxLength = Math.max(maxLength, j - i + 1);
                }
            }
        }
        return maxLength;
    }
}
```
### Algorithm
- Initialize `maxLength = 0`.
- Use two nested loops with indices `i` and `j` to generate all possible substrings `s.substring(i, j + 1)`.
- For each substring, create a helper function or an inner block of code to check if it's 'awesome'.
- To check if a substring is awesome:
  - Create a frequency array of size 10 for digits '0' through '9'.
  - Iterate through the substring's characters to populate the frequency array.
  - Count how many digits have an odd frequency.
  - If the number of digits with odd frequencies is 0 or 1, the substring is awesome.
- If the current substring is awesome, update `maxLength = max(maxLength, j - i + 1)`.
- After checking all substrings, return `maxLength`.

## Optimized Brute Force
This approach improves upon the naive brute-force method by optimizing the frequency counting step. Instead of re-calculating the frequencies for every substring from scratch, we can maintain a running count. As we extend the substring by one character at a time, we update the frequency map and the count of digits with odd frequencies in constant time.
**Time:** O(N^2), where N is the length of the string. The two nested loops dominate the runtime, and the work inside the inner loop is constant time. · **Space:** O(1), as the frequency map requires constant space.
**Pros:** A significant improvement over the O(N^3) approach.; Still relatively easy to reason about.
**Cons:** Still too slow for the given constraints, leading to a Time Limit Exceeded error.
### Explanation
We iterate through all possible starting positions `i`. For each `i`, we iterate from `j = i` to the end of the string, effectively considering all substrings starting at `i`. We maintain a frequency count of digits for the current substring `s[i..j]`. When we move from `j` to `j+1`, we just update the count for the new character `s[j+1]`. This avoids the third loop of the naive approach, reducing the complexity.

```java
class Solution {
    public int longestAwesome(String s) {
        int n = s.length();
        int maxLength = 0;
        if (n == 0) return 0;

        for (int i = 0; i < n; i++) {
            int[] freq = new int[10];
            int oddCount = 0;
            for (int j = i; j < n; j++) {
                int digit = s.charAt(j) - '0';
                
                freq[digit]++;
                if (freq[digit] % 2 != 0) {
                    oddCount++;
                } else {
                    oddCount--;
                }

                if (oddCount <= 1) {
                    maxLength = Math.max(maxLength, j - i + 1);
                }
            }
        }
        return maxLength;
    }
}
```
### Algorithm
- Initialize `maxLength = 0`.
- Use an outer loop to iterate through each possible start index `i` of a substring.
- For each `i`, initialize a frequency array `freq` of size 10 and a variable `oddCount = 0`.
- Start an inner loop for the end index `j` from `i` to `n-1`.
- In the inner loop, for each character `s[j]`, update its frequency in `freq`.
- As you update the frequency, also update `oddCount`. If the frequency of the current digit becomes odd, increment `oddCount`; if it becomes even, decrement `oddCount`.
- After updating, if `oddCount <= 1`, it means the substring `s[i..j]` is awesome. Update `maxLength = max(maxLength, j - i + 1)`.
- Return `maxLength` after the loops complete.

## Prefix Masks and Hashing
This is the most efficient approach, solving the problem in linear time. It leverages bitmasks to track the parity of digit counts and a hash map (or an array) to store the first occurrences of these parity states. This allows us to find the longest awesome substring in a single pass through the string.
**Time:** O(N), where N is the length of the string. We iterate through the string once. Inside the loop, we perform a constant number of operations (a fixed loop of 10 for checking one-bit-off masks). · **Space:** O(1). The space is dominated by the `firstOccurrence` array. Since there are `2^10 = 1024` possible masks, the space required is constant and does not depend on the input size N.
**Pros:** Highly efficient with linear time complexity.; Optimal solution that passes for all given constraints.
**Cons:** The logic involving bitmasks and prefix states can be less intuitive to come up with compared to brute-force methods.
### Explanation
We use a bitmask to represent the parity of the counts of digits '0'-'9' in a prefix of the string. A 10-bit integer is sufficient, where the `i`-th bit is 1 if the digit `i` has appeared an odd number of times, and 0 otherwise. The mask for a substring `s[i..j]` is simply the XOR of the prefix masks for `s[0..j]` and `s[0..i-1]`.

A substring is awesome if its mask is either 0 (all even counts) or a power of 2 (one odd count). We iterate through the string, calculating the prefix mask at each position `i`. We use an array `firstOccurrence` to store the earliest index at which we've seen each mask. For each position `i`, we check for previously seen masks that would result in an awesome substring and update our `maxLength` accordingly.

```java
import java.util.Arrays;

class Solution {
    public int longestAwesome(String s) {
        int n = s.length();
        // An array is faster than a HashMap. Size is 2^10 = 1024.
        int[] firstOccurrence = new int[1024];
        // Initialize with a value larger than any possible index.
        Arrays.fill(firstOccurrence, n); 
        
        int mask = 0;
        int maxLength = 0;
        
        // Base case for prefixes that are awesome themselves.
        // A mask of 0 at index -1 means a prefix of length i - (-1) = i + 1.
        firstOccurrence[0] = -1;

        for (int i = 0; i < n; i++) {
            // Update the mask with the current character's digit.
            mask ^= (1 << (s.charAt(i) - '0'));

            // Case 1: The substring has all characters with even counts.
            maxLength = Math.max(maxLength, i - firstOccurrence[mask]);

            // Case 2: The substring has one character with an odd count.
            for (int j = 0; j < 10; j++) {
                int testMask = mask ^ (1 << j);
                maxLength = Math.max(maxLength, i - firstOccurrence[testMask]);
            }

            // Store the first occurrence of the current mask if not already stored.
            if (firstOccurrence[mask] == n) { // Use n as the 'not found' value
                firstOccurrence[mask] = i;
            }
        }
        return maxLength;
    }
}
```
### Algorithm
- The core idea is that a string can form a palindrome if at most one of its character counts is odd.
- We can track the parity (even/odd) of counts of the 10 digits using a 10-bit integer mask. The `d`-th bit is 1 if digit `d` has an odd count, 0 otherwise.
- The mask for a substring `s[i..j]` can be found by `prefix_mask[j] ^ prefix_mask[i-1]`.
- The problem then becomes finding two indices `i` and `j` such that the XOR of their prefix masks is either 0 (all even counts) or a power of two (one odd count), while maximizing `j-i`.
- We can solve this in one pass:
  1. Initialize an array `firstOccurrence` of size 1024 to store the first index seen for each mask. Initialize it with a value indicating 'not seen' (e.g., a value larger than any valid index).
  2. Set `firstOccurrence[0] = -1` to handle awesome prefixes correctly.
  3. Initialize `mask = 0` and `maxLength = 0`.
  4. Iterate through the string from `i = 0` to `n-1`:
     a. Update `mask` by XORing with `1 << (s.charAt(i) - '0')`.
     b. **Case 1 (Even Palindrome):** Check if `mask` has been seen before. If `firstOccurrence[mask]` exists, it means the substring between that first occurrence and `i` has a mask of 0. Update `maxLength = max(maxLength, i - firstOccurrence[mask])`.
     c. **Case 2 (Odd Palindrome):** For each digit `d` from 0 to 9, create a `testMask = mask ^ (1 << d)`. If `firstOccurrence[testMask]` exists, it means the substring has one odd count. Update `maxLength = max(maxLength, i - firstOccurrence[testMask])`.
     d. If the current `mask` is seen for the first time, record its index: `firstOccurrence[mask] = i`.
  5. Return `maxLength`.

# Solutions
### Java

```java
class Solution {
public
  int longestAwesome(String s) {
    int[] d = new int[1024];
    int st = 0, ans = 1;
    Arrays.fill(d, -1);
    d[0] = 0;
    for (int i = 1; i <= s.length(); ++i) {
      int v = s.charAt(i - 1) - '0';
      st ^= 1 << v;
      if (d[st] >= 0) {
        ans = Math.max(ans, i - d[st]);
      } else {
        d[st] = i;
      }
      for (v = 0; v < 10; ++v) {
        if (d[st ^ (1 << v)] >= 0) {
          ans = Math.max(ans, i - d[st ^ (1 << v)]);
        }
      }
    }
    return ans;
  }
}

```

### CPP

```cpp
class Solution {
public:
  int longestAwesome(string s) {
    vector<int> d(1024, -1);
    d[0] = 0;
    int st = 0, ans = 1;
    for (int i = 1; i <= s.size(); ++i) {
      int v = s[i - 1] - '0';
      st ^= 1 << v;
      if (~d[st]) {
        ans = max(ans, i - d[st]);
      } else {
        d[st] = i;
      }
      for (v = 0; v < 10; ++v) {
        if (~d[st ^ (1 << v)]) {
          ans = max(ans, i - d[st ^ (1 << v)]);
        }
      }
    }
    return ans;
  }
};

```

### Python

```python
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

```