1930. Unique Length-3 Palindromic Subsequences

Leetcode link

题目简介

/**
 * @param {string} s
 * @return {number}
 */

题目给我们一个只包含小写字母的字符串 s，要求我们从中找出有多少对不重复的长度为 3 的回文子字符串

解题思路

由于题目只要求长度为 3 所以我们可以先找到字符串中重复字母最左的下标与最右的下标，然后遍历下标范围内不重复的字符个数就可以了

由于字符串 s 中只包含小写的字符，所以我们可以用长度为 26 的数组来保存我们所需的下标信息

Javascript

/**
 * @param {string} s
 * @return {number}
 */
var countPalindromicSubsequence = function (s) {
    const BASELINE = 'a'.charCodeAt(0)
    const firstIdxArr = new Array(26).fill(Infinity)
    const lastIdxArr = new Array(26).fill(-1)
    let res = 0

    for (let i = 0; i < s.length; i++) {
        const pos = s[i].charCodeAt(0) - BASELINE
        if (firstIdxArr[pos] === Infinity) {
            firstIdxArr[pos] = i
        }
        lastIdxArr[pos] = i
    }

    for (j = 0; j < 26; j++) {
        const left = firstIdxArr[j]
        const right = lastIdxArr[j]
        if (left >= right) {
            continue
        }

        const seenLetters = new Array(26).fill(false)
        for (let k = left + 1; k < right; k++) {
            seenLetters[s[k].charCodeAt(0) - BASELINE] = true
        }
        res += seenLetters.reduce((acc, cur) => acc + (cur ? 1 : 0), 0)
    }

    return res
};