GeezerVison

The World Wide Web, restored to 800 pixels of glory.

GeezerVison is showing leetcodejavascript.com — #1542 - Find Longest Awesome Substring - LeetCode JavaScript Solutions

Back to all solutions

#1542 - Find Longest Awesome Substring

Hard • View on LeetCode • View on GitHub

String Hash Table Bit Manipulation

Problem 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.

Solution

/**
 * @param {string} s
 * @return {number}
 */
var longestAwesome = function(s) {
  let result = 0;
  let prefixMask = 0;
  const digitMasks = new Map();
  digitMasks.set(0, -1);

  for (let i = 0; i < s.length; i++) {
    const digit = s.charCodeAt(i) - '0'.charCodeAt(0);
    prefixMask ^= (1 << digit);

    if (digitMasks.has(prefixMask)) {
      result = Math.max(result, i - digitMasks.get(prefixMask));
    } else {
      digitMasks.set(prefixMask, i);
    }

    for (let j = 0; j < 10; j++) {
      const oddMask = prefixMask ^ (1 << j);
      if (digitMasks.has(oddMask)) {
        result = Math.max(result, i - digitMasks.get(oddMask));
      }
    }
  }

  return result;
};

You are visitor 01402520 — GeezerVison does not store the pages you look up.
Best viewed with Netscape Navigator 4.7 or Internet Explorer 6 at 800×600. No cookies required.