1177.构建回文串检测.md

1177.构建回文串检测

/*
 * @lc app=leetcode.cn id=1177 lang=typescript
 *
 * [1177] 构建回文串检测
 */

// @lc code=start
function canMakePaliQueries(s: string, queries: number[][]): boolean[] {}
// @lc code=end

解法 1: 前缀和

function canMakePaliQueries(s: string, queries: number[][]): boolean[] {
  const n = s.length
  const cnt = Array.from({ length: n }, () => [])
  for (let i = 0; i < n; i++) {
    cnt[i] = [...(cnt[i - 1] ?? new Array(26).fill(0))]
    cnt[i][s.charCodeAt(i) - 97]++
  }
  const res: boolean[] = []
  for (let [l, r, k] of queries) {
    let d = 0
    for (let i = 0; i < 26; i++) {
      d += (cnt[r][i] - (cnt[l - 1]?.[i] ?? 0)) & 1
    }
    if ((r - l + 1) & 1) {
      d--
    }
    res.push(d / 2 <= k)
  }
  return res
}

Case

test.each([
  {
    input: {
      s: 'abcda',
      queries: [
        [3, 3, 0],
        [1, 2, 0],
        [0, 3, 1],
        [0, 3, 2],
        [0, 4, 1],
      ],
    },
    output: [true, false, false, true, true],
  },
  {
    input: {
      s: 'lyb',
      queries: [
        [0, 1, 0],
        [2, 2, 1],
      ],
    },
    output: [false, true],
  },
])('input: s = $input.s, queries = $input.queries', ({ input: { s, queries }, output }) => {
  expect(canMakePaliQueries(s, queries)).toEqual(output)
})