0730. Count Different Palindromic Subsequences

题目信息

题号:

0730

难度:

Hard

主题:

字符串、回文子序列、去重计数

原题:

LeetCode 0730

重点:

统计不同的非空回文子序列字符串,相同字符序列即使由不同下标选出也只计一次;结果对 10^9 + 7 取模

题目重述

给定字符串 s,统计其中可以得到多少种不同的非空回文子序列,并返回该数量对 10^9 + 7 取模后的结果。

子序列可以通过删除原字符串中的任意若干字符得到,未删除字符的相对顺序必须保持不变,不要求连续。只有正读和反读完全相同的非空子序列才算回文。计数按最终字符序列去重:同一个回文字符串即使能由多组不同下标构成,也只计一次。

s 的长度在 [1, 1000] 范围内,并且只包含字符 a、b、c、d。

自建示例

不同下标产生相同子序列时去重:

输入:s = "aba"
输出:4
解释:不同的非空回文子序列为 "a"、"b"、"aa" 和 "aba"。字符 "a" 可从两个位置分别选出,但最终字符串相同,只计一次。

全部字符相同:

输入:s = "aaaa"
输出:4
解释:不同的回文子序列只有 "a"、"aa"、"aaa" 和 "aaaa";同一长度的多种下标选择不会增加计数。