【算法题-困难】最长超赞子字符串

困难算法题，最长超赞子字符串，使用 JavaScript 语言编写

题目

给你一个字符串 s 。请返回 s 中最长的 超赞子字符串 的长度。

「超赞子字符串」需满足满足下述两个条件：

• 该字符串是 s 的一个非空子字符串
• 进行任意次数的字符交换后，该字符串可以变成一个回文字符串
• 1 <= s.length <= 10^5
• s 仅由数字组成

输入格式

输入一行只包含数字的字符串s

输出格式

输出s中最长的 超赞子字符串 的长度

输入样例

输入样例一：

3242415

输出样例

5

“24241” 是最长的超赞子字符串，交换其中的字符后，可以得到回文 “24142”

分析

要找到字符串 s 中最长的“超赞子字符串”的长度，我们需要利用回文字符串的特性。一个字符串可以通过任意次数的字符交换变成回文字符串，当且仅当最多只有一个字符出现奇数次。

步骤:

1. 使用位掩码表示字符频率：我们可以使用一个整数的二进制表示来记录每个字符的奇偶性。例如，mask 的第 i 位为 1 表示字符 i 出现了奇数次，为 0 表示字符 i 出现了偶数次。
2. 前缀和思想：我们使用一个哈希表 prefixMask 来记录每个前缀的位掩码第一次出现的位置。
3. 遍历字符串：在遍历字符串的过程中，我们更新当前的 mask，并检查当前 mask 是否已经在 prefixMask 中出现过。如果出现过，我们可以计算出当前子字符串的长度。
4. 检查单个字符的变化：为了处理最多一个字符出现奇数次的情况，我们需要检查当前 mask 与每个可能的单字符变化后的 mask 是否在 prefixMask 中出现过。

解答

// 这是题目要求的输入格式
let inputs = `
3242415
`;

inputs = inputs.trim();

function longestAwesome(s) {
  let maxLength = 0;
  // 单独一个数字也算回文
  for (let i = 0; i < s.length; i++) {
    // 数字出现的次数（0-9）
    const showTimes = new Array(10).fill(0);
    for (let j = i; j < s.length; j++) {
      showTimes[s[j]]++;
      
      let oddCounts = 0;
      // 0-9 出现的次数为奇数的个数
      for (let k = 0; k < 10; k++) {
        if (showTimes[k] % 2 !== 0) {
          oddCounts++;
        }
      }
      if (oddCounts <= 1) {
        maxLength = Math.max(j - i + 1, maxLength);
      }
    }
  }
  return maxLength;
}

// 示例
console.log(longestAwesome(inputs)); // 5

解释