Problem

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.

Examples

Example 1

1
2
3

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

Example 2

1
2
3

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

Example 3

1
2
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.

Solution

Method 1 – Dynamic Programming with Last Occurrence

Intuition

Every new character can be added to all existing subsequences to form new ones, but we must avoid double-counting subsequences that end with the same character seen before.

Approach

  1. Let dp[i] be the number of distinct subsequences for the prefix of length i.
  2. For each character, double the count (add the character to all previous subsequences), but subtract the count from the last time this character appeared.
  3. Use an array to track the last position of each character.
  4. Return dp[n] - 1 (subtract the empty subsequence).

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

class Solution {
public:
    int distinctSubseqII(string s) {
        int n = s.size(), mod = 1e9+7;
        vector<int> dp(n+1); dp[0] = 1;
        vector<int> last(26, -1);
        for (int i = 0; i < n; ++i) {
            dp[i+1] = (2LL * dp[i]) % mod;
            int c = s[i] - 'a';
            if (last[c] != -1) dp[i+1] = (dp[i+1] - dp[last[c]] + mod) % mod;
            last[c] = i;
        }
        return (dp[n] - 1 + mod) % mod;
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

func distinctSubseqII(s string) int {
    n, mod := len(s), int(1e9+7)
    dp := make([]int, n+1)
    dp[0] = 1
    last := make([]int, 26)
    for i := range last { last[i] = -1 }
    for i := 0; i < n; i++ {
        dp[i+1] = (2 * dp[i]) % mod
        c := int(s[i] - 'a')
        if last[c] != -1 {
            dp[i+1] = (dp[i+1] - dp[last[c]] + mod) % mod
        }
        last[c] = i
    }
    return (dp[n] - 1 + mod) % mod
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

class Solution {
    public int distinctSubseqII(String s) {
        int n = s.length(), mod = 1000000007;
        int[] dp = new int[n+1]; dp[0] = 1;
        int[] last = new int[26]; Arrays.fill(last, -1);
        for (int i = 0; i < n; ++i) {
            dp[i+1] = (2 * dp[i]) % mod;
            int c = s.charAt(i) - 'a';
            if (last[c] != -1) dp[i+1] = (dp[i+1] - dp[last[c]] + mod) % mod;
            last[c] = i;
        }
        return (dp[n] - 1 + mod) % mod;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

class Solution {
    fun distinctSubseqII(s: String): Int {
        val n = s.length
        val mod = 1_000_000_007
        val dp = IntArray(n+1); dp[0] = 1
        val last = IntArray(26) { -1 }
        for (i in 0 until n) {
            dp[i+1] = (2L * dp[i] % mod).toInt()
            val c = s[i] - 'a'
            if (last[c] != -1) dp[i+1] = (dp[i+1] - dp[last[c]] + mod) % mod
            last[c] = i
        }
        return (dp[n] - 1 + mod) % mod
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

class Solution:
    def distinctSubseqII(self, s: str) -> int:
        n, mod = len(s), 10**9+7
        dp = [1] + [0]*n
        last = [-1]*26
        for i, ch in enumerate(s):
            dp[i+1] = 2 * dp[i] % mod
            c = ord(ch) - ord('a')
            if last[c] != -1:
                dp[i+1] = (dp[i+1] - dp[last[c]] + mod) % mod
            last[c] = i
        return (dp[n] - 1) % mod
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

impl Solution {
    pub fn distinct_subseq_ii(s: String) -> i32 {
        let n = s.len();
        let modn = 1_000_000_007;
        let mut dp = vec![1; n+1];
        let mut last = vec![-1; 26];
        let s: Vec<u8> = s.into_bytes();
        for i in 0..n {
            dp[i+1] = (2 * dp[i]) % modn;
            let c = (s[i] - b'a') as usize;
            if last[c] != -1 {
                dp[i+1] = (dp[i+1] - dp[last[c] as usize] + modn) % modn;
            }
            last[c] = i as i32;
        }
        ((dp[n] - 1 + modn) % modn) as i32
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

class Solution {
    distinctSubseqII(s: string): number {
        const n = s.length, mod = 1e9+7;
        const dp = Array(n+1).fill(0); dp[0] = 1;
        const last = Array(26).fill(-1);
        for (let i = 0; i < n; i++) {
            dp[i+1] = (2 * dp[i]) % mod;
            const c = s.charCodeAt(i) - 97;
            if (last[c] !== -1) dp[i+1] = (dp[i+1] - dp[last[c]] + mod) % mod;
            last[c] = i;
        }
        return (dp[n] - 1 + mod) % mod;
    }
}

Complexity

  • ⏰ Time complexity: O(n) where n is the length of the string. Each character is processed once.
  • 🧺 Space complexity: O(n) for the DP array.