3121. 统计特殊字符的数量

3121. Count the Number of Special Characters II

定长数组 O(1) 空间

function numberOfSpecialChars(word: string): number {
  const lastLower = new Array(26).fill(-1)
  const firstUpper = new Array(26).fill(Infinity)
  // 原代码这里叫 firstLower，命名错误——存的明明是大写首次出现位置

  for (let i = 0; i < word.length; i++) {
    const ch = word[i]
    if (ch >= 'a' && ch <= 'z') {
      lastLower[ch.charCodeAt(0) - 97] = i
    } else {
      const idx = ch.charCodeAt(0) - 65
      if (firstUpper[idx] === Infinity) firstUpper[idx] = i
    }
  }

  let count = 0
  for (let i = 0; i < 26; i++) {
    if (lastLower[i] !== -1 && firstUpper[i] !== Infinity && lastLower[i] < firstUpper[i]) {
      count++
    }
  }
  return count
}

时间 $O(n)$，空间 $O(1)$，零堆分配。lastLower[idx] 每次覆写保留最后出现位置，firstUpper[idx] 只记首次。

第一种写法的思路是边走边用 Set 维护候选项：

function numberOfSpecialChars_set(word: string): number {
  if (word.length < 2) return 0
  const upperSeen = new Set<string>()
  const lowerCandidates = new Set<string>()

  for (const ch of word) {
    if (ch >= 'a' && ch <= 'z') {
      // 大写已经出现过 → 这个小写不可能作为「最后一个小写」
      if (upperSeen.has(ch.toUpperCase())) {
        lowerCandidates.delete(ch)
        continue
      }
      lowerCandidates.add(ch)
    } else {
      upperSeen.add(ch)
    }
  }

  // 不在 forEach 里直接 delete——虽然 spec 允许但不同引擎实现有差异
  const toRemove: string[] = []
  for (const c of lowerCandidates) {
    if (!upperSeen.has(c.toUpperCase())) toRemove.push(c)
  }
  for (const c of toRemove) lowerCandidates.delete(c)

  return lowerCandidates.size
}

Set 版每次迭代有 toUpperCase() 分配临时 String + hash 查找，常数比数组版大一个数量级。$n$ 到 $10^5$ 频繁调用时，临时 String 会填满新生代触发 minor GC。

本质是把「过程中不断判断集合关系」拆成「收集极值 → 一次比较」：对每个字母只关心 $max(L)$ 和 $min(U)$，遍历完比大小即可，逻辑彻底解耦。

定长数组替代 Set 的前提：key 空间已知且有限（26 字母、10 数字、128 ASCII），每个 slot 只存标量。不满足这条件就别这么干。