DEV Community
·
1930. 唯一长度为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)复杂度算法通过前缀和后缀字符的跟踪，显著提高了计算效率。这种方法适合处理较长字符串（最大长度可达10^5），在实际应用中能够快速得出结果，避免了暴力搜索的低效。
唯一性的重要性
在计算长度为3的回文子序列时，文章强调了唯一性，即相同的子序列只计数一次。这一特性在实际应用中可以避免重复计算，提高结果的准确性，尤其在处理大数据时尤为重要。
延伸问答
如何计算长度为3的唯一回文子序列数量？
通过跟踪前缀和后缀字符，检查每个字符作为中间字符的有效组合，可以在O(n)的复杂度内计算。
什么是回文和子序列？
回文是正反读相同的字符串，子序列是从原字符串中删除某些字符后形成的新字符串。
给定字符串's'，如何判断是否存在长度为3的回文子序列？
可以通过检查前缀和后缀字符组合来判断，若没有有效组合则返回0。
能否给出一些示例来说明回文子序列的计算？
例如，输入's'为'aabca'时，输出为3，回文子序列为'aba'、'aaa'、'aca'。
该算法的时间和空间复杂度是多少？
时间复杂度为O(n)，空间复杂度为O(n)。
如何确保不重复计数相同的回文子序列？
使用哈希集合存储唯一的回文子序列，确保每个子序列只计数一次。
