【Leetcode】1930. 长度为 3 的不同回文子序列

这一题题目不难理解，就是在字符串中寻找有多少个独一无二的回文，只不过这个回文可以不相邻，而且长度只有3。固定首尾，然后再确定中间的字符，加一个去重即可(Set)。

时间复杂度过大，n的3次方

这里的思路比较耿直，直接用3层循环来做
i来寻找首，j来寻找尾，k在中间进行累加即可
最后利用set来进行去重
只不过这里不能ac，时间复杂度过大。

1var countPalindromicSubsequence = function (s) {
2    let set = new Set();
3    for (let i = 0; i < s.length; ++i) {
4        for (let j = s.length - 1; j > i + 1; --j) {
5            if (s[i] === s[j]) {
6                for (let k = i + 1; k < j; ++k) {
7                    set.add(s[i] + s[k] + s[j]);
8                }
9            }
10        }
11    }
12    return set.size
13};
14

ac

这个解法时间复杂度就是n，准确来说是26*n，存在常数，即O(n)
寻找每个字符首次出现的位置，还有最后一次出现的位置
如果这两个位置的字符索引不相等，那么就可以形成回文

1var countPalindromicSubsequence = function (s) {
2    const firstIndex = new Array(26).fill(-1)
3    const lastIndex = new Array(26).fill(-1)
4    for(let i = 0; i < s.length; ++i){
5        const charCode = s.charCodeAt(i) - 'a'.charCodeAt(0)
6        if(firstIndex[charCode] === -1){
7            firstIndex[charCode] = i
8        }
9        lastIndex[charCode] = i
10    }
11    let sum = 0
12    for(let i = 0; i < 26; ++i){
13        let first = firstIndex[i]
14        let last = lastIndex[i]
15        if(first == last) continue
16        let charSet = new Set()
17        for(let j = first + 1; j < last; ++j){
18            charSet.add(s[j])
19        }
20        sum += charSet.size
21    }
22    return sum
23};
24

《【Leetcode】1930. 长度为 3 的不同回文子序列》 是转载文章，点击查看原文。