LeetCode: Distinct Subsequences II

Posted on August 5, 2019July 26, 2020 by braindenny

Distinct Subsequences II

Similar Problems:

Given a string S, count the number of distinct, non-empty subsequences of S .

Since the result may be large, return the answer modulo 10^9 + 7.

Example 1:

Input: "abc"
Output: 7
Explanation: The 7 distinct subsequences are "a", "b", "c", "ab", "ac", "bc", and "abc".

Example 2:

Input: "aba"
Output: 6
Explanation: The 6 distinct subsequences are "a", "b", "ab", "ba", "aa" and "aba".

Example 3:

Input: "aaa"
Output: 3
Explanation: The 3 distinct subsequences are "a", "aa" and "aaa".

Note:

S contains only lowercase letters.
1 <= S.length <= 2000

Github: code.dennyzhang.com

Credits To: leetcode.com

Leave me comments, if you have better ways to solve.

Solution:

// https://code.dennyzhang.com/distinct-subsequences-ii
// Basic Ideas: dynamic programming
//
//  The idea of post-trie
//
//  dp[i]: count of distinct subsquence, with S[i] taken
//         prev subsequences + S[i] -> new subsequences
//
//  Notice: how to merge the same ending character?
//   Input: "aba"
//   Current parsed: "ab"
//
//    endswith 'a': ["a"]
//    endswith 'b': ["ab","b"]
//
//    Now parsing: aba
//    l['a'-'a'] -> build from others + 1 (myself)
//
// Complexity: Time O(n) Space O(1)
import "math"
func distinctSubseqII(S string) int {
    mod := int(math.Pow(10, 9)+7)
    l := make([]int, 26)
    for i, _ := range S {
        v := int(S[i] - 'a')
        sum := 0
        for _, c := range l {
            sum = sum + c
        }
        l[v] = (sum + 1) % mod
    }
    res := 0
    for _, c := range l {
        res += c
    }
    res = res % mod
    return res
}

Post Views: 0