0940. Distinct Subsequences II

题目信息

题号:

0940

难度:

Hard

主题:

字符串、非空子序列、去重计数

原题:

LeetCode 0940

重点:

子序列通过删除任意字符并保持相对顺序得到;只按最终字符串内容去重,不统计空子序列,结果需要取模

题目重述

给定只包含小写英文字母的字符串 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",空字符串不计入答案。