Daily LeetCode – day0077 0940. Distinct Subsequences II

// 0940. Distinct Subsequences II
class Solution {
    public int distinctSubseqII(String s) {
        char[] chars = s.toCharArray();
        int len = chars.length;
        final int MOD = 1000000007;
        int[] lastTimeIncrementByLetter = new int[123];
        int[] subsequences = new int[len];
        subsequences[0] = 2;
        lastTimeIncrementByLetter[chars[0]] = 1;
        for (int i = 1; i < len; ++i) {
            int previous = subsequences[i - 1];
            subsequences[i] = (previous * 2 % MOD - lastTimeIncrementByLetter[chars[i]] % MOD + MOD) % MOD;
            lastTimeIncrementByLetter[chars[i]] = previous;
        }
        return subsequences[len - 1] - 1;
    }
}

学习笔记：
今天是一道困难题唯一子序列。
看了题解后发现这道题的递推原来是用哈希表记录上一次出现这个字母的添加的数量，然后这次减去。这其实就是可能重复的情况了。
这道题还有一点恶心的就是数量可能很大，需要模，模结果也不对，模前面也不对。是需要前面模，后面模，减完整个再模。属实烦啊。