1763.最长的美好子字符串.md

1763.最长的美好子字符串

/*
 * @lc app=leetcode.cn id=1763 lang=typescript
 *
 * [1763] 最长的美好子字符串
 */

// @lc code=start
function longestNiceSubstring(s: string): string {}
// @lc code=end

解法 1: 暴力枚举

function longestNiceSubstring(s: string): string {
  let res = '',
    len = 0
  for (let i = 0; i < s.length; i++) {
    next: for (let j = i + len + 1; j <= s.length; j++) {
      const sub = s.slice(i, j)
      const set = new Set(sub)
      for (let char of set) {
        if (!set.has(char.toLocaleLowerCase()) || !set.has(char.toLocaleUpperCase())) continue next
      }
      res = sub
      len = j - i
    }
  }
  return res
}

解法 2: 滑动窗口

function longestNiceSubstring(s: string): string {
  const max = [...new Set(s.split('').map(a => a.toLocaleLowerCase()))].length
  const map = new Map<string, number>()
  const check = () => {
    for (let i = 0; i < 26; i++) {
      const char = String.fromCharCode(i + 97)
      if (
        (!map.get(char) && map.get(char.toLocaleUpperCase())) ||
        (map.get(char) && !map.get(char.toLocaleUpperCase()))
      )
        return false
    }
    return true
  }
  const set = new Set<string>()

  let resl = 0,
    resr = 0
  for (let len = max; len > 0; len--) {
    for (let l = 0, r = 0; l < s.length; l++) {
      while (r < s.length && (set.size < len || set.has(s[r].toLocaleLowerCase()))) {
        set.add(s[r].toLocaleLowerCase())
        map.set(s[r], (map.get(s[r]) ?? 0) + 1)
        r++
      }

      if (set.size === len && check()) {
        if (r - l > resr - resl || (r - l === resr - resl && l < resl)) [resr, resl] = [r, l]
      }

      map.set(s[l], map.get(s[l])! - 1)
      if (!map.get(s[l])) {
        map.delete(s[l])
      }
      if (!map.get(s[l].toLocaleLowerCase()) && !map.get(s[l].toLocaleUpperCase())) {
        set.delete(s[l].toLocaleLowerCase())
      }
    }
  }
  return s.slice(resl, resr)
}

Case

test.each([
  { input: { s: 'YazaAay' }, output: 'aAa' },
  { input: { s: 'Bb' }, output: 'Bb' },
  { input: { s: 'c' }, output: '' },
])('input: s = $input.s', ({ input: { s }, output }) => {
  expect(longestNiceSubstring(s)).toEqual(output)
})