0730. Count Different Palindromic Subsequences¶
题目信息¶
- 题号:
0730
- 难度:
Hard
- 主题:
字符串、回文子序列、去重计数
- 原题:
- 重点:
统计不同的非空回文子序列字符串,相同字符序列即使由不同下标选出也只计一次;结果对
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";同一长度的多种下标选择不会增加计数。