2022-10-01：给定一个字符串 s，计算 s 的 不同非空子序列 的个数 因为结果可能很大，所以返回答案需要对 10^9 + 7 取余 。 字符串的 子序列 是经由原字符串删除一些（也可能不删除

2022-10-01：给定一个字符串 s，计算 s 的 不同非空子序列 的个数
因为结果可能很大，所以返回答案需要对 10^9 + 7 取余 。
字符串的 子序列 是经由原字符串删除一些（也可能不删除）字符
但不改变剩余字符相对位置的一个新字符串。
输入: s = “abc”。
输出: 7。

答案2022-10-01：

dp[0~25]，保存26个字母结尾的子序列个数。
时间复杂度：O(N)。
空间复杂度：O(1)。

代码用rust编写。代码如下：

use std::collections::HashMap;
fn main() {let ans = distinct_subseq_ii("bccaccbaabbc");println!("ans = {}", ans);let ans = zuo("bccaccbaabbc");println!("ans = {}", ans);
}fn distinct_subseq_ii(s: &str) -> i32 {if s.len() == 0 {return 0;}let m = 1000000007;let str2: Vec<u8> = s.bytes().collect();// a -> 0 ->// b -> 1 ->// c -> 2 ->// z -> 25 ->// count[i] = 0let mut count = [0; 26];// { }let mut all = 1; // 算空集for x in str2.iter() {// x// 纯新增// add = all - count[x]// all += add// count[x] + addlet add = (all - count[(*x - 'a' as u8) as usize] + m) % m;all = (all + add) % m;count[(*x - 'a' as u8) as usize] = (count[(*x - 'a' as u8) as usize] + add) % m;}// {} 去掉！return all - 1;
}
fn zuo(s: &str) -> i32 {if s.len() == 0 {return 0;}let m = 1000000007;let str2: Vec<u8> = s.bytes().collect();let mut map: HashMap<u8, i32> = HashMap::new();let mut all = 1; // 一个字符也没遍历的时候，有空集for x in str2.iter() {let new_add = all;//			int curAll = all + newAdd - (map.containsKey(x) ? map.get(x) : 0);let mut cur_all = all;cur_all = (cur_all + new_add) % m;cur_all = (cur_all- if map.contains_key(x) {*map.get(x).unwrap()} else {0}+ m)% m;all = cur_all;map.insert(*x, new_add);}return all - 1;
}

执行结果如下：

左神java代码