0940. Distinct Subsequences II¶
题目信息¶
- 题号:
0940
- 难度:
Hard
- 主题:
字符串、非空子序列、去重计数
- 原题:
- 重点:
子序列通过删除任意字符并保持相对顺序得到;只按最终字符串内容去重,不统计空子序列,结果需要取模
题目重述¶
给定只包含小写英文字母的字符串 s。可以删除任意数量的字符而不改变剩余字符的相对顺序,从而得到一个子序列。
请统计能够得到多少种内容互不相同的非空子序列。由不同下标选择得到但最终字符序列相同的结果只计一次;空字符串不计入。返回答案对 10^9 + 7 取模后的值。
1 <= s.length <= 2000。
自建示例¶
末尾字符与开头重复:
输入:s = "abca"
输出:14
解释:不同非空子序列为 a、b、c、aa、ab、ac、ba、bc、ca、aba、abc、aca、bca、abca,共 14 种;两个位置产生的相同内容只计一次。
字符串只有一个字符:
输入:s = "z"
输出:1
解释:唯一非空子序列是 "z",空字符串不计入答案。