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

🟠   🔖  位运算 哈希表 字符串 前缀和  🔗 力扣 LeetCode

题目

Given a string s, return the number ofunique palindromes of length three that are a subsequence of s.

Note that even if there are multiple ways to obtain the same subsequence, it is still only counted once.

A palindrome is a string that reads the same forwards and backwards.

A subsequence of a string is a new string generated from the original string with some characters (can be none) deleted without changing the relative order of the remaining characters.

• For example, "ace" is a subsequence of "abcde ".

Example 1:

Input: s = "aabca"

Output: 3

Explanation: The 3 palindromic subsequences of length 3 are:

• "aba" (subsequence of "a a b c a ")
• "aaa" (subsequence of "aa bc a ")
• "aca" (subsequence of "a ab ca ")

Example 2:

Input: s = "adc"

Output: 0

Explanation: There are no palindromic subsequences of length 3 in "adc".

Example 3:

Input: s = "bbcbaba"

Output: 4

Explanation: The 4 palindromic subsequences of length 3 are:

• "bbb" (subsequence of "bb c b aba")
• "bcb" (subsequence of "b b cb aba")
• "bab" (subsequence of "b bcb ab a")
• "aba" (subsequence of "bbcb aba ")

Constraints:

• 3 <= s.length <= 10^5
• s consists of only lowercase English letters.

题目大意

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

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

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

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

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

示例 1：

输入： s = "aabca"

输出： 3

解释： 长度为 3 的 3 个回文子序列分别是：

• "aba" ("a a** b** c** a** " 的子序列)
• "aaa" ("aa bc** a** " 的子序列)
• "aca" ("a ab** ca** " 的子序列)

示例 2：

输入： s = "adc"

输出： 0

解释： "adc" 不存在长度为 3 的回文子序列。

示例 3：

输入： s = "bbcbaba"

输出： 4

解释： 长度为 3 的 4 个回文子序列分别是：

• "bbb" ("bb c** b** aba" 的子序列)
• "bcb" ("b b** cb** aba" 的子序列)
• "bab" ("b bcb** ab** a" 的子序列)
• "aba" ("bbcb** aba** " 的子序列)

提示：

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

解题思路

1. 获取唯一字符集合：

   • 使用 Set 收集字符串中的所有唯一字符，逐个字符作为回文子序列的首尾字符来统计。

2. 遍历字符集合：

   • 对于每个字符 letter，在字符串 s 中找到它的第一次出现位置和最后一次出现位置。
   • 如果 letter 在字符串中至少出现两次，则提取 letter 的第一次出现和最后一次出现之间的子字符串。

3. 统计中间字符：

   • 对上述子字符串使用 Set 去重，统计中间字符的种类数量。
   • 将该数量累加到结果 res 中。

4. 返回结果。

复杂度分析

• 时间复杂度：O(n)
  • 构建唯一字符集合：O(n)，其中 n 是字符串长度。
  • 对每个唯一字符，找到它的首次和末次出现位置：O(n)。
  • 提取子字符串并统计中间字符：O(n)。
  • 总复杂度为 O(n * |letters|)，其中 |letters| 是唯一字符的个数，最坏情况下为 26。
• 空间复杂度：O(n)，存储唯一字符集合和中间字符集合。

代码

/**
 * @param {string} s
 * @return {number}
 */
var countPalindromicSubsequence = function (s) {
	const letters = new Set(s);
	let res = 0;

	for (let letter of letters) {
		let start = -1,
			end = 0;

		// 找到字符的首次和末次出现位置
		for (let i = 0; i < s.length; i++) {
			if (s.charAt(i) === letter) {
				if (start === -1) start = i;
				end = i;
			}
		}

		// 如果有有效范围，统计中间字符的数量
		if (start < end) {
			const middleChars = new Set(s.slice(start + 1, end));
			res += middleChars.size;
		}
	}

	return res;
};

相关题目

题号	标题	题解	标签	难度	力扣
2484	统计回文子序列数目		字符串 动态规划	🔴	🀄️ 🔗