不同的子序列 II

/*
 * 思路：
 * 1. 使用动态规划结合Java Stream API。
 * 2. 用一个数组dp记录前i个字符的不同非空子序列个数。
 * 3. 使用一个数组last来记录每个字符上一次出现的位置。
 * 4. 最终答案需要对10^9 + 7取余。
 */
import java.util.stream.IntStream;
public class Solution {
    public int distinctSubseqII(String s) {
        int MOD = 1000000007;
        int n = s.length();
        int[] dp = new int[n + 1];
        int[] last = new int[26];
        dp[0] = 1;
        IntStream.range(1, n + 1).forEach(i -> {
            char c = s.charAt(i - 1);
            dp[i] = (dp[i - 1] * 2 % MOD - (last[c - 'a'] > 0 ? dp[last[c - 'a'] - 1] : 0) + MOD) % MOD;
            last[c - 'a'] = i;
        });
        return dp[n] - 1;
    }
}