1781.所有子字符串美丽值之和.md

1781.所有子字符串美丽值之和

/*
 * @lc app=leetcode.cn id=1781 lang=typescript
 *
 * [1781] 所有子字符串美丽值之和
 */

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

解法 1: 暴力枚举

function beautySum(s: string): number {
  const n = s.length
  let res = 0
  for (let i = 0; i < n; i++) {
    const cnt: number[] = new Array(26).fill(0),
      cnt1: Set<number>[] = []
    let min = 1,
      max = 1
    for (let j = i; j < n; j++) {
      const ch = s.charCodeAt(j) - 97
      if (cnt[ch]) {
        cnt1[cnt[ch]].delete(ch)
        if (min === cnt[ch] && cnt1[cnt[ch]].size === 0) min++
      } else min = 1
      cnt[ch]++
      if (!cnt1[cnt[ch]]) cnt1[cnt[ch]] = new Set()
      cnt1[cnt[ch]].add(ch)
      if (cnt[ch] > max) max = cnt[ch]
      res += max - min
    }
  }
  return res
}

Case

test.each([
  { input: { s: 'aabcb' }, output: 5 },
  { input: { s: 'aabcbaa' }, output: 17 },
])('input: s = $input.s', ({ input: { s }, output }) => {
  expect(beautySum(s)).toEqual(output)
})