1542. Find Longest Awesome Substring

Description

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.

 

Solutions

Solution: Bit Manipulation

• Time complexity: O(10n -> n)
• Space complexity: O(1024 -> 1)

 

JavaScript

/**
 * @param {string} s
 * @return {number}
 */
const longestAwesome = function (s) {
  const n = s.length;
  const prefixIndex = Array.from({ length: 1 << 10 }, () => n);
  let bitmask = 0;
  let result = 0;

  prefixIndex[0] = -1;

  for (let index = 0; index < n; index++) {
    bitmask ^= 1 << Number(s[index]);

    result = Math.max(index - prefixIndex[bitmask], result);

    for (let num = 0; num < 10; num++) {
      const prevIndex = prefixIndex[bitmask ^ (1 << num)];

      result = Math.max(index - prevIndex, result);
    }

    prefixIndex[bitmask] = Math.min(index, prefixIndex[bitmask]);
  }

  return result;
};