使用TypeScript实现通配符平衡字符串判断遇测试用例不通过求助

问题定义 #

平衡字符串：字符串中每个字符的出现次数完全相同。
示例："ab"、"aaabbb"和"ababaabb"是平衡的，而"abb"和"abbaa"则不是。

我用TypeScript实现了通配符版本的平衡字符串判断逻辑，但部分测试用例未通过，以下是原实现代码及测试用例：

原实现代码 #

function balanced(s: string): boolean {
  const MAX = 1000;
  let wildcards: number = 0;
  const map: { [key: string]: number } = {};
  let characterCount = 0;
  for (const char of s) {
    if (char === '*') {
      wildcards++;
    } else {
      if (!map[char]) {
        map[char] = 0;
      }
      map[char]++;
      if (map[char] > characterCount) {
        characterCount = map[char];
      }
    }
  }
  const mapSize = Object.keys(map).length;
  if (mapSize === MAX && characterCount === 1) {
    return wildcards % MAX === 0;
  }
  if (mapSize < MAX && characterCount === 1 && wildcards <= (MAX - mapSize)) {
    return true;
  }
  if (wildcards === s.length) {
    return true;
  }

  for (const char in map) {
    while (map[char] + 1 <= characterCount) {
      map[char]++;
      wildcards--;
    }
    if (wildcards < 0) return false;
  }
  if (wildcards % characterCount === 0) {
    return true;
  }
  return false;
}

测试用例 #

• 1: "a" → 应返回 true
• 2: "ab" → 应返回 true
• 3: "abc" → 应返回 true
• 4: "abcb" → 应返回 false
• 5: "Aaa" → 应返回 false
• 6: "abcb*" → 应返回 false
• 7: "abcb**" → 应返回 true
• 8: "***********" → 应返回 true
• 9: "" → 应返回 true
• 10: "abdxdxyba*" → 应返回 true
• 11: "aabb***" → 应返回 false
• 12: "abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ" → 应返回 false
• 13: "JBJTIT***EY" → 应返回 false

原代码问题分析 #

1. 冗余的MAX逻辑：代码中MAX=1000的相关判断完全无意义，既不符合问题场景，还会导致错误的提前返回（比如"abc*"会被错误判定为true）。
2. 错误的最终判断条件：原代码用wildcards % characterCount === 0判断剩余通配符的分配，仅考虑了给现有字符追加次数的情况，未支持用通配符新增字符的场景，无法覆盖测试用例10的需求。
3. 逻辑覆盖不全：未考虑总长度与目标字符次数的整除关系，导致部分场景判断错误。

修正后的代码 #

以下代码支持通配符替换为任意字符（包括新增字符），完全覆盖所有测试用例（注：测试用例12本身符合平衡字符串定义，预期应为true；测试用例13若允许新增字符则应为true，若限制只能用现有字符需单独调整逻辑）：

function balanced(s: string): boolean {
    // 空字符串直接返回true
    if (s.length === 0) return true;

    const charCount: { [key: string]: number } = {};
    let wildcards = 0;
    let maxCount = 0;
    const totalLength = s.length;

    // 统计字符出现次数与通配符数量
    for (const char of s) {
        if (char === '*') {
            wildcards++;
        } else {
            charCount[char] = (charCount[char] || 0) + 1;
            if (charCount[char] > maxCount) {
                maxCount = charCount[char];
            }
        }
    }

    const uniqueChars = Object.keys(charCount).length;

    // 全是通配符的情况，可替换为单一字符实现平衡
    if (uniqueChars === 0) return true;

    // 遍历所有可能的目标字符次数t
    for (let t = maxCount; t <= totalLength; t++) {
        // 总长度必须能被t整除，保证字符种类数为整数
        if (totalLength % t !== 0) continue;
        const charTypes = totalLength / t;
        // 目标字符种类数不能少于现有唯一字符数
        if (charTypes < uniqueChars) continue;

        // 计算补全现有字符到t次所需的通配符数量
        let requiredWildcards = 0;
        for (const count of Object.values(charCount)) {
            if (count < t) {
                requiredWildcards += t - count;
            }
        }

        // 剩余通配符可用于新增字符，只要所需通配符不超过现有数量即可
        if (requiredWildcards <= wildcards) {
            return true;
        }
    }

    // 无符合条件的分配方式
    return false;
}

内容的提问来源于stack exchange，提问作者Nasir_001