《算法题 - 最小覆盖子串》

function minWindow(s: string, t: string): string {
  // t 剩余匹配总长度
  let tLeftSize = t.length
  // t 每个字母对应出现次数表
  const tCharCountMap = {}

  for (const char of t) {
    if (!tCharCountMap[char]) {
      tCharCountMap[char] = 0
    }
    tCharCountMap[char]++
  }

  let globalResult = ''

  for (let i = 0; i < s.length; i++) {
    let currentResult = ''
    let currentTLeftSize = tLeftSize
    const currentTCharCountMap = { ...tCharCountMap }

    // 找到以 i 下标开头，满足条件的字符串
    for (let j = i; j < s.length; j++) {
      currentResult += s[j]
      
      // 如果这一项在 t 中存在，则减 1
      if (currentTCharCountMap[s[j]] !== undefined && currentTCharCountMap[s[j]] !== 0) {
        currentTCharCountMap[s[j]]--
        currentTLeftSize--
      }

      // 匹配完了
      if (currentTLeftSize === 0) {
        if (globalResult === '') {
          globalResult = currentResult
        } else if (currentResult.length < globalResult.length) {
          globalResult = currentResult
        }
        break
      }
    }
  }

  return globalResult
};

function minWindow(s: string, t: string): string {
  // s 每个字母出现次数表
  const sCharMap = {}
  // t 每个字母对应出现次数表
  const tCharMap = {}
  // 未覆盖的字符有哪些
  const notCoverChar = new Set<string>()

  // 计算各字符在 t 出现次数
  for (const char of t) {
    if (!tCharMap[char]) {
      tCharMap[char] = 0
    }
    tCharMap[char]++
    notCoverChar.add(char)
  }

  let leftIndex = 0
  let rightIndex = -1
  let result = ''
  let currentStr = ''

  // leftIndex | rightIndex 超限才会停止
  while (leftIndex < s.length && rightIndex < s.length) {
    // 未覆盖的条件：notCoverChar 长度 > 0
    if (notCoverChar.size > 0) {
      // 此时窗口没有 cover t，rightIndex 右移寻找
      rightIndex++
      const nextChar = s[rightIndex]
      currentStr += nextChar
      if (sCharMap[nextChar] === undefined) {
        sCharMap[nextChar] = 0
      }
      sCharMap[nextChar]++
      // 如果 tCharMap 有这个 nextChar, 且已收集数量超过 t 中数量，此 char ready
      if (
        tCharMap[nextChar] !== undefined &&
        sCharMap[nextChar] >= tCharMap[nextChar]
      ) {
        notCoverChar.delete(nextChar)
      }
    } else {
      // 此时窗口正好 cover t，记录最短结果
      if (result === '') {
        result = currentStr
      } else if (currentStr.length < result.length) {
        result = currentStr
      }
      // leftIndex 即将右移，将 sCharMap 中对应 char 数量减 1
      const previousChar = s[leftIndex]
      sCharMap[previousChar]--
      // 如果 previousChar 在 sCharMap 数量少于 tCharMap 数量，则不能 cover
      if (sCharMap[previousChar] < tCharMap[previousChar]) {
        notCoverChar.add(previousChar)
      }
      // leftIndex 右移
      leftIndex++
      currentStr = currentStr.slice(1, currentStr.length)
    }
  }
  
  return result
};