难度: Hard
给定一个字符串 s，计算 s 的 不同非空子序列 的个数。因为结果可能很大，所以返回答案需要对 10^9 + 7 取余 。
字符串的 子序列 是经由原字符串删除一些（也可能不删除）字符但不改变剩余字符相对位置的一个新字符串。
"ace" 是 "abcde" 的一个子序列，但 "aec" 不是。示例 1：
输入：s = "abc" 输出：7 解释：7 个不同的子序列分别是 "a", "b", "c", "ab", "ac", "bc", 以及 "abc"。
示例 2：
输入：s = "aba" 输出：6 解释：6 个不同的子序列分别是 "a", "b", "ab", "ba", "aa" 以及 "aba"。
示例 3：
输入：s = "aaa" 输出：3 解释：3 个不同的子序列分别是 "a", "aa" 以及 "aaa"。
提示：
1 <= s.length <= 2000s 仅由小写英文字母组成运行时间: 36 ms
内存: 16.0 MB
class Solution:
def distinctSubseqII(self, s: str) -> int:
mod=1000000007 #模数
s=list(s)
#将a-z转成0-25
for i in range(len(s)):
s[i]=ord(s[i])-ord('a')
endCnt=[0]*26 #endCnt[i]表示以i结尾的子序列个数
newAdd=0 #表示每轮纯新增的子序列个数(排除掉与之前重复的)
ans=1 #记录字符串s的子序列个数 初始认为是1(包括空集,最后减掉即可)
for x in s:
newAdd=ans-endCnt[x] #纯新增个数
endCnt[x]+=newAdd #更新以该字符结尾的子序列个数
ans=ans%mod+newAdd%mod #更新答案个数
return (ans-1+mod)%mod
这个题解使用了动态规划的思想来计算所有的不同子序列。具体方法是用一个数组endCnt来记录以每个字符结尾的子序列的数量。对于字符串s中的每个字符x，当前所有的子序列可以与x组合形成新的子序列，而新形成的以x结尾的子序列的数量就是在x加入之前的所有子序列数量减去上一次以x结尾的子序列数量。这样可以保证计数的过程中不会重复计算相同的子序列。最终结果需要减去初始化时候计入的空子序列。
时间复杂度: O(n)
空间复杂度: O(1)
# Solution class to compute different subsequences
class Solution:
def distinctSubseqII(self, s: str) -> int:
mod = 1000000007 # Use mod to avoid large numbers
s = list(s) # Convert string to list for easier manipulation
# Convert characters from 'a'-'z' to 0-25
for i in range(len(s)):
s[i] = ord(s[i]) - ord('a')
endCnt = [0] * 26 # Array to store subsequences count ending with each letter
newAdd = 0 # Store count of new subsequences added in each iteration
ans = 1 # Initial count includes empty subsequence
for x in s:
newAdd = ans - endCnt[x] # Calculate new subsequences excluding those ending with current char previously
endCnt[x] += newAdd # Update count of subsequences ending with current char
ans = (ans + newAdd) % mod # Update total count and apply mod
return (ans - 1 + mod) % mod # Exclude the empty subsequence and apply mod
是的，初始化ans为1而不是0是因为在动态规划的过程中已经考虑了空子序列。空子序列是任何字符串的有效子序列之一，因此在开始计算时将其包含进总数。这样做可以简化后续的计算，因为每个新字符引入时，都可以默认存在与空子序列结合成新子序列的情形。
这样做的目的是为了避免重复计数。在动态规划过程中，每个字符x加入到现有的所有子序列中会形成新的子序列，但如果直接加上前面所有的子序列总数，会重复计算以x结尾的子序列。通过减去上一次以该字符x结尾的子序列数量，我们确保每次加入的都是新生成的、独特的子序列，而不包括之前已经计算过的以x结尾的子序列。
通过减去以当前字符结尾的上一次的子序列数量，我们确保每次添加的子序列都是基于当前字符新形成的。这意味着每个新形成的子序列都是从当前字符和之前计算的所有独立子序列组合而成，而不包括任何之前已经存在的以该字符结尾的子序列。这种方法确保了算法在更新子序列计数时不会出现重复，从而保持了算法的正确性。
直接返回ans - 1在大多数情况下是没有问题的。然而考虑到ans可能为0（尤其是在空字符串或者其他特殊情况下），直接做减法可能导致结果为负数。在编程实现中，返回负数可能不符合预期的输出要求。通过添加mod并取模，确保最终结果始终为非负整数，并且在处理大数时防止溢出，符合模运算的常规操作。