一、题目
给定一个字符串 s，计算 s 的 不同非空子序列 的个数。因为结果可能很大，所以返回答案需要对 10^9 + 7 取余 。
字符串的 子序列 是经由原字符串删除一些（也可能不删除）字符但不改变剩余字符相对位置的一个新字符串。
例如："ace" 是 "abcde" 的一个子序列，但 "aec" 不是。
二、示例
2.1> 示例 1：
【输入】s = "abc"
【输出】7
【解释】7 个不同的子序列分别是 "a", "b", "c", "ab", "ac", "bc", 以及 "abc"。
2.2> 示例 2：
【输入】s = "aba"
【输出】6
【解释】6 个不同的子序列分别是 "a", "b", "ab", "ba", "aa" 以及 "aba"。
2.3> 示例 3：
【输入】s = "aaa"
【输出】3
【解释】3 个不同的子序列分别是 "a", "aa" 以及 "aaa"。
提示：
1<= s.length <=2000s仅由小写英文字母组成
三、解题思路
根据题目描述，要找出一个字符串中所有不同的子序列。那么我们就需要找出这种子序列组合的规律。为了排除其他干扰，我们假设字符串中素有的字符都是不重复的。如下图所示，s=“abcd”，那么我们可以看到如下规律：
- 遍历第1个字符‘a’：子序列总数 = 1（字符‘a’本身）=
1- 遍历第2个字符‘b’：子序列总数 =【字符'a'的子序列总数】+ 1（字符‘b’本身）= 1 + 1 =
2；- 遍历第3个字符‘c’：子序列总数 =【字符'a'的子序列总数】+ 【字符'b'的子序列总数】+ 1（字符‘c’本身）= 1 + 2 + 1 =
4；- 遍历第4个字符‘d’：子序列总数 =【字符'a'的子序列总数】+【字符'b'的子序列总数】+【字符'c'的子序列总数】+ 1（字符‘d’本身）= 1 + 2 + 4 + 1 =
8；- 【总结果】 = 1 + 2 + 4 + 8 = 15
但是，题目中并没有限制字符不能重复，所以，我们这时候在考虑如果字符串中出现重复字符，对总结果的影响是怎样的？请见下图，我们以s=“abcb”为例，我们发现，里面有字符‘b’发生了重复，我们发现如下规律：
在第1次遍历到字符‘b’的时候：子序列为“
ab”、“b”；
在第2次遍历到字符‘b’的时候：子序列为“ab”、“b”、“abb”、“bb”、“acb”、“abcb”、“bcb”、“cb”；
【结论】我们发现第2次遍历字符'b'的时候，已经包含了第1次遍历字符'b'的子序列了。所以，在统计最终结果的时候，我们需要把“上一次”相同字符子序列总数减去才可以。
基本思路就是这样了，具体代码实现，请参照如下部分。
四、代码实现
class Solution {
public int distinctSubseqII(String s) {
int mod = (int)1e9 + 7;
long result = 0L;
long[] letter = new long[26]; // 记录26个字符每个字符的子序列总数
for (char sc : s.toCharArray()) {
long pre = letter[sc - 'a']; // 获得字符sc前一次统计的子序列数
letter[sc - 'a'] = (result + 1) % mod; // 计算当前字符sc的子序列数
result = (result + letter[sc - 'a'] - pre + mod) % mod; // 加mod的目的是为了防止结果溢出为负数
}
return (int)result;
}
}
今天的文章内容就这些了：
写作不易，笔者几个小时甚至数天完成的一篇文章，只愿换来您几秒钟的 点赞 & 分享 。
更多技术干货，欢迎大家关注公众号“爪哇缪斯” ~ \(^o^)/ ~ 「干货分享，每天更新」