What is the fastest way to count unique length-3 palindromic subsequences?

Use a hash table to track first and last occurrences of each character and then collect unique middle characters for each outer pair.

Can this method handle strings up to length 10^5?

Yes, the O(n) linear approach with constant space scales efficiently for strings of maximum allowed length.

Why do we use a set for middle characters?

Using a set ensures that duplicates are not counted multiple times for the same outer character, preserving uniqueness.

Does this approach extend to palindromes longer than 3 characters?

The same outer-inner indexing idea works, but longer lengths require careful nested iteration or additional prefix tracking.

How does this relate to the Hash Table plus String pattern?

The pattern is applied by mapping characters to positions in a hash table and using string indices to efficiently find valid palindromic subsequences.

#1930

Medium

auto_awesome前缀和

LeetCode 题解工作台

长度为 3 的不同回文子序列

给你一个字符串 s ，返回 s 中长度为 3 的不同回文子序列的个数。即便存在多种方法来构建相同的子序列，但相同的子序列只计数一次。回文是正着读和反着读一样的字符串。子序列是由原字符串删除其中部分字符（也可以不删除）且不改变剩余字符之间相对顺序形成的一个新字符串。例如， "ace"…

哈希表字符串位运算前缀和

题目描述

给你一个字符串 s ，返回 s 中 长度为 3 的不同回文子序列 的个数。

即便存在多种方法来构建相同的子序列，但相同的子序列只计数一次。

回文是正着读和反着读一样的字符串。

子序列 是由原字符串删除其中部分字符（也可以不删除）且不改变剩余字符之间相对顺序形成的一个新字符串。

例如，"ace" 是 "abcde" 的一个子序列。

示例 1：

输入：s = "aabca"
输出：3
解释：长度为 3 的 3 个回文子序列分别是：
- "aba" ("aabca" 的子序列)
- "aaa" ("aabca" 的子序列)
- "aca" ("aabca" 的子序列)

示例 2：

输入：s = "adc"
输出：0
解释："adc" 不存在长度为 3 的回文子序列。

示例 3：

输入：s = "bbcbaba"
输出：4
解释：长度为 3 的 4 个回文子序列分别是：
- "bbb" ("bbcbaba" 的子序列)
- "bcb" ("bbcbaba" 的子序列)
- "bab" ("bbcbaba" 的子序列)
- "aba" ("bbcbaba" 的子序列)

提示：

3 <= s.length <= 10⁵
s 仅由小写英文字母组成

lightbulb

解题思路

方法一：枚举两端字符 + 哈希表

由于字符串中只包含小写字母，因此我们可以直接枚举所有的两端字符。对于每一对两端字符 $c$ ，我们找出它们在字符串中第一次和最后一次出现的位置 $l$ 和 $r$ ，如果 $r - l > 1$ ，说明找到了满足条件的回文序列，我们将 $[l+1,..r-1]$ 之间的字符去重后统计个数，即为以 $c$ 为两端字符的回文序列个数，加入答案中。

枚举结束后，即可得到答案。

1

2

3

4

5

6

7

8

9

class Solution:
    def countPalindromicSubsequence(self, s: str) -> int:
        ans = 0
        for c in ascii_lowercase:
            l, r = s.find(c), s.rfind(c)
            if r - l > 1:
                ans += len(set(s[l + 1 : r]))
        return ans

speed

复杂度分析

指标	值
时间	complexity is O(n) because we scan the string once and check fixed 26 letters for each character. Space complexity is O(1) since only a constant-size array or hash table for 26 letters is used.
空间	O(1)

psychology

面试官常问的追问

外企场景

question_mark
Can you find a linear-time approach without generating all subsequences explicitly?
question_mark
How would you handle counting duplicates efficiently for the same outer character?
question_mark
Consider leveraging the fixed alphabet size to simplify the solution.

warning

常见陷阱

外企场景

error
Attempting to generate all length-3 subsequences leads to O(n^3) time and timeouts.
error
Counting duplicate palindromes multiple times instead of using sets or hash tables.
error
Ignoring the character position constraints when identifying valid middle characters.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Count unique length-4 palindromic subsequences with the same hash table approach.
arrow_right_alt
Return all unique length-3 palindromic subsequences instead of just counting them.
arrow_right_alt
Apply the same method to strings with digits or uppercase letters by expanding the hash table.

help

常见问题

外企场景

继续练习

#1915 最美子字符串的数目 #1371 每个元音包含偶数次的最长子字符串 #1177 构建回文串检测