DEV Community
·
1930. 唯一长度为3的回文子序列
💡
原文英文，约600词，阅读约需3分钟。
📝
内容提要
给定字符串s，计算长度为3的唯一回文子序列数量。回文是正反读相同的字符串，子序列是删除某些字符后的新字符串。通过跟踪前缀和后缀字符，可以在O(n)的复杂度内有效找到所有有效的回文子序列。
🎯
关键要点
- 给定字符串s，计算长度为3的唯一回文子序列数量。
- 回文是正反读相同的字符串，子序列是删除某些字符后的新字符串。
- 即使有多种方式获得相同的子序列，也只计数一次。
- 示例1：输入s = 'aabca'，输出3，回文子序列为'aba'、'aaa'、'aca'。
- 示例2：输入s = 'adc'，输出0，没有长度为3的回文子序列。
- 示例3：输入s = 'bbcbaba'，输出4，回文子序列为'bbb'、'bcb'、'bab'、'aba'。
- 约束条件：3 <= s.length <= 105，s仅包含小写字母。
- 使用前缀和后缀字符跟踪的高效算法来计算有效的回文子序列。
- 前缀数组存储每个位置左侧遇到的字符集合。
- 后缀数组存储每个位置右侧遇到的字符集合。
- 考虑每个字符作为长度为3的回文的中间字符，检查有效的前缀和后缀字符组合。
- 使用哈希集合存储唯一的回文子序列，确保不重复计数。
- 时间复杂度为O(n)，空间复杂度为O(n)。
❓
延伸问答
如何计算长度为3的唯一回文子序列数量？
通过跟踪前缀和后缀字符，检查每个字符作为中间字符的有效组合，可以在O(n)的复杂度内计算。
什么是回文和子序列？
回文是正反读相同的字符串，子序列是从原字符串中删除某些字符后形成的新字符串。
给定字符串's'，如何判断是否存在长度为3的回文子序列？
可以通过检查前缀和后缀字符组合来判断，若没有有效组合则返回0。
能否给出一些示例来说明回文子序列的计算？
例如，输入's'为'aabca'时，输出为3，回文子序列为'aba'、'aaa'、'aca'。
该算法的时间和空间复杂度是多少？
时间复杂度为O(n)，空间复杂度为O(n)。
如何确保不重复计数相同的回文子序列？
使用哈希集合存储唯一的回文子序列，确保每个子序列只计数一次。
➡️
