Find longest awesome substring

Hash Table String Bit Manipulation

46.6% acceptance

Feb 25, 2026

889

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.

Solution

Rust

Time O(n²)

Space O(n)

LeetCode

solution.rs

impl Solution {
  pub fn longest_awesome(s: String) -> i32 {
    // XOR bitmask of digit parities. Palindrome-able iff at most 1 bit set.
    let mut first = vec![-2i32; 1024]; // -2 = not seen
    first[0] = -1; // empty prefix at index -1
    let mut mask = 0usize;
    let mut ans = 1i32;
    for (i, b) in s.bytes().enumerate() {
      mask ^= 1 << ((b - b'0') as usize);
      // 0 odd-frequency digits
      if first[mask] != -2 {
        ans = ans.max(i as i32 - first[mask]);
      } else {
        first[mask] = i as i32;
      }
      // 1 odd-frequency digit
      for d in 0..10 {
        let m = mask ^ (1 << d);
        if first[m] != -2 {
          ans = ans.max(i as i32 - first[m]);
        }
      }
    }
    ans
  }
}