Skip to content

940. Distinct Subsequences II

Description

Given a string s, return the number of distinct non-empty subsequences of s. Since the answer may be very large, return it modulo 109 + 7.

A subsequence of a string is a new string that is formed from the original string by deleting some (can be none) of the characters without disturbing the relative positions of the remaining characters. (i.e., "ace" is a subsequence of "abcde" while "aec" is not.

 

Example 1:

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

Example 2:

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

Example 3:

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

 

Constraints:

  • 1 <= s.length <= 2000
  • s consists of lowercase English letters.

Solutions

Solution 1: Dynamic Programming

Thinking

Count distinct nonempty subsequences. \(n\le 2000\), so listing subsets is impossible. Classify by last letter: \(f[c]\) is the number of distinct subsequences now ending with \(c\). On reading \(c\), it may follow any previous subsequence or stand alone, so \(f[c]\leftarrow \sum f+1\); a repeated \(c\) overwrites the old family that ended with \(c\).

We define \(f[i]\) as the number of distinct subsequences ending with the \(i\)-th lowercase letter. Initially, all elements in \(f\) are \(0\).

Traverse the string \(s\). For the current character \(c\), update \(f[c]\) to \(\sum_{i=0}^{25} f[i] + 1\). Here \(\sum_{i=0}^{25} f[i]\) is the number of distinct subsequences obtained so far, and \(+1\) means the character \(c\) itself can also be a subsequence.

Finally, the answer is \(\sum_{i=0}^{25} f[i]\) modulo \(10^9 + 7\).

The time complexity is \(O(n \times C)\), and the space complexity is \(O(C)\), where \(n\) is the length of \(s\) and \(C\) is the size of the character set. In this problem, \(C = 26\).

1
2
3
4
5
6
7
class Solution:
    def distinctSubseqII(self, s: str) -> int:
        mod = 10**9 + 7
        f = [0] * 26
        for c in s:
            f[ord(c) - ord("a")] = (sum(f) + 1) % mod
        return sum(f) % mod

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
class Solution {
    public int distinctSubseqII(String s) {
        final int mod = (int) 1e9 + 7;
        int[] f = new int[26];
        for (int i = 0; i < s.length(); ++i) {
            int x = 1;
            for (int v : f) {
                x = (x + v) % mod;
            }
            f[s.charAt(i) - 'a'] = x;
        }
        int ans = 0;
        for (int v : f) {
            ans = (ans + v) % mod;
        }
        return ans;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
    int distinctSubseqII(string s) {
        const int mod = 1e9 + 7;
        int f[26]{};
        for (char& c : s) {
            int x = 1;
            for (int v : f) {
                x = (x + v) % mod;
            }
            f[c - 'a'] = x;
        }
        int ans = 0;
        for (int v : f) {
            ans = (ans + v) % mod;
        }
        return ans;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
func distinctSubseqII(s string) int {
    const mod int = 1e9 + 7
    f := [26]int{}
    for _, c := range s {
        x := 1
        for _, v := range f {
            x = (x + v) % mod
        }
        f[c-'a'] = x
    }
    ans := 0
    for _, v := range f {
        ans = (ans + v) % mod
    }
    return ans
}

1
2
3
4
5
6
7
8
function distinctSubseqII(s: string): number {
    const mod = 1e9 + 7;
    const f: number[] = Array(26).fill(0);
    for (const c of s) {
        f[c.charCodeAt(0) - 97] = f.reduce((acc, v) => (acc + v) % mod, 1);
    }
    return f.reduce((acc, v) => (acc + v) % mod);
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
impl Solution {
    pub fn distinct_subseq_ii(s: String) -> i32 {
        const MOD: i32 = 1_000_000_007;
        let mut f = [0; 26];
        for u in s.bytes() {
            let mut x = 1;
            for &v in &f {
                x = (x + v) % MOD;
            }
            f[(u - b'a') as usize] = x;
        }
        f.iter().fold(0, |acc, &v| (acc + v) % MOD)
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
int distinctSubseqII(char* s) {
    const int mod = 1e9 + 7;
    int f[26] = {0};
    for (int i = 0; s[i]; ++i) {
        int x = 1;
        for (int j = 0; j < 26; ++j) {
            x = (x + f[j]) % mod;
        }
        f[s[i] - 'a'] = x;
    }
    int ans = 0;
    for (int i = 0; i < 26; ++i) {
        ans = (ans + f[i]) % mod;
    }
    return ans;
}

Solution 2: Optimized Dynamic Programming

Thinking

Method 1 rescans \(26\) cells on every update. Keep the running sum \(\textit{ans}\); the increment is \(\textit{ans}-f[i]+1\), so both \(f[i]\) and \(\textit{ans}\) update in \(O(1)\).

Based on Solution 1, we can maintain a variable \(\textit{ans}\) as the sum of all elements in \(f\). Each time we update \(f[i]\), the number of newly added distinct subsequences is \(\textit{ans} - f[i] + 1\). We then update both \(\textit{ans}\) and \(f[i]\) accordingly.

The time complexity is \(O(n)\), and the space complexity is \(O(C)\).

Similar problems:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
class Solution:
    def distinctSubseqII(self, s: str) -> int:
        mod = 10**9 + 7
        f = [0] * 26
        ans = 0
        for c in s:
            i = ord(c) - ord("a")
            add = (ans + 1 - f[i]) % mod
            ans = (ans + add) % mod
            f[i] = (f[i] + add) % mod
        return ans

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
class Solution {
    public int distinctSubseqII(String s) {
        final int mod = (int) 1e9 + 7;
        int[] f = new int[26];
        int ans = 0;
        for (int i = 0; i < s.length(); ++i) {
            int j = s.charAt(i) - 'a';
            int add = (ans + 1 + mod - f[j]) % mod;
            ans = (ans + add) % mod;
            f[j] = (f[j] + add) % mod;
        }
        return ans;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
class Solution {
public:
    int distinctSubseqII(string s) {
        const int mod = 1e9 + 7;
        int f[26]{};
        int ans = 0;
        for (char& c : s) {
            int i = c - 'a';
            int add = (ans + 1 + mod - f[i]) % mod;
            ans = (ans + add) % mod;
            f[i] = (f[i] + add) % mod;
        }
        return ans;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
func distinctSubseqII(s string) int {
    const mod int = 1e9 + 7
    f := [26]int{}
    ans := 0
    for _, c := range s {
        i := c - 'a'
        add := (ans + 1 + mod - f[i]) % mod
        ans = (ans + add) % mod
        f[i] = (f[i] + add) % mod
    }
    return ans
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
function distinctSubseqII(s: string): number {
    const mod = 1e9 + 7;
    const f: number[] = Array(26).fill(0);
    let ans = 0;
    for (const c of s) {
        const i = c.charCodeAt(0) - 97;
        const add = (ans + 1 + mod - f[i]) % mod;
        ans = (ans + add) % mod;
        f[i] = (f[i] + add) % mod;
    }
    return ans;
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
impl Solution {
    pub fn distinct_subseq_ii(s: String) -> i32 {
        const MOD: i32 = 1_000_000_007;
        let mut f = [0; 26];
        let mut ans = 0;
        for u in s.bytes() {
            let i = (u - b'a') as usize;
            let add = (ans + 1 + MOD - f[i]) % MOD;
            ans = (ans + add) % MOD;
            f[i] = (f[i] + add) % MOD;
        }
        ans
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
int distinctSubseqII(char* s) {
    const int mod = 1e9 + 7;
    int f[26] = {0};
    int ans = 0;
    for (int i = 0; s[i]; ++i) {
        int j = s[i] - 'a';
        int add = (ans + 1LL + mod - f[j]) % mod;
        ans = (ans + add) % mod;
        f[j] = (f[j] + add) % mod;
    }
    return ans;
}

Comments