940. Distinct Subsequences II - Solution

Q: Is Distinct Subsequences II easy or hard?

Distinct Subsequences II is classified as a Hard problem because it requires careful dynamic programming state design and handling of duplicate subsequences. Many candidates initially overcount results until they recognize the need to subtract contributions from previous occurrences.

Q: Distinct Subsequences II Python/Java solution

Python and Java implementations follow the same dynamic programming formula: dp[i] = 2 * dp[i-1] minus the count before the last occurrence of the current character. Both languages usually store last positions in an array or dictionary and apply modulo 1e9+7 to avoid overflow.

Q: How to solve Distinct Subsequences II in O(n)?

Use dynamic programming where dp[i] represents the number of distinct subsequences using the first i characters. For each new character, double the previous count and subtract the contribution from its previous occurrence to remove duplicates. Tracking last positions with an array or hash map ensures the algorithm processes the string in linear time.

Q: What is the best approach for Distinct Subsequences II?

The best approach uses dynamic programming with a last-seen index for each character. Each step doubles the number of subsequences and subtracts duplicates created by earlier occurrences of the same character. This method runs in O(n) time and handles repeated characters correctly using a hash map or fixed array.

Q: Is Distinct Subsequences II asked at Google/Amazon/Meta?

Distinct subsequence counting problems appear frequently in interviews at companies like Google, Amazon, and Meta because they test dynamic programming reasoning and duplicate handling. Variations of this problem are commonly used to evaluate DP state design and optimization skills.

Q: What data structure is used in Distinct Subsequences II?

The solution primarily uses dynamic programming along with an auxiliary structure to track the last occurrence of each character. This is typically implemented using a hash map or a fixed array of size 26 for lowercase letters. These structures help subtract duplicate subsequences efficiently.

Q: What is the time complexity of Distinct Subsequences II?

The optimal solution runs in O(n) time where n is the length of the string. Each character is processed once while updating the dynamic programming state and checking the previous occurrence of the character. Space complexity is O(n) for the DP array or O(1) with the space‑optimized version.

The 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 10⁹ + 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.

Approach overview

Problem Overview: Given a string s, count the number of distinct non‑empty subsequences. Subsequences can be formed by deleting characters without changing the order. Duplicate subsequences caused by repeated characters must only be counted once, and the result is returned modulo 1e9 + 7.

Approach 1: Dynamic Programming with Last Seen (O(n) time, O(n) space)

This solution uses dynamic programming where dp[i] represents the number of distinct subsequences considering the first i characters. Each new character doubles the number of subsequences because every existing subsequence can either include or exclude it. However, if the character appeared before, some subsequences would be counted twice. Track the previous index of each character using a lastSeen array or map and subtract the count that existed before its previous occurrence.

The transition becomes dp[i] = 2 * dp[i-1] - dp[last[c]-1]. This subtraction removes duplicate subsequences created by the earlier occurrence of the same character. A hash map or fixed array tracks the last position of each character. Time complexity is O(n) because each character is processed once, and space complexity is O(n) for the DP table.

Approach 2: Space Optimized Dynamic Programming (O(n) time, O(1) space)

The DP array can be eliminated by storing only the contribution of subsequences that end with each character. Maintain an array end[26] where end[c] stores how many distinct subsequences currently end with character c. For each character in the string, compute the total number of subsequences so far, then update the value for that character while removing the previous contribution for duplicates.

This approach effectively tracks how many subsequences each character contributes to the final count, preventing double counting when the same letter appears again. Because the alphabet size is fixed, the memory usage becomes constant. Time complexity remains O(n) and space complexity drops to O(1).

Recommended for interviews: Interviewers usually expect the dynamic programming with last‑seen correction. It shows you understand how duplicate subsequences arise and how DP states evolve. The space‑optimized version demonstrates deeper insight by reducing memory while keeping the same O(n) time complexity.

Approach 1: Dynamic Programming with Last Seen

This approach applies dynamic programming by maintaining an array dp where dp[i] represents the number of distinct subsequences for the substring ending at the i-th character. Another structure is used to track when each character was last seen to handle duplicate contributions.

Python

def distinctSubseqII(s: str) -> int:
    MOD = 10**9 + 7
    dp = [0] * (len(s) + 1)
    dp[0] = 1
    lastIndex = {}

    for i, char in enumerate(s):
        dp[i + 1] = (dp[i] * 2) % MOD
        if char in lastIndex:
            dp[i + 1] = (dp[i + 1] - dp[lastIndex[char]] + MOD) % MOD
        lastIndex[char] = i

    return (dp[len(s)] - 1) % MOD  # Subtracting the empty subsequence

print(distinctSubseqII("abc"))  # Output: 7

Java

import java.util.*;

class Solution {
    public int distinctSubseqII(String s) {
        int n = s.length();
        final int MOD = 1_000_000_007;
        int[] dp = new int[n + 1];
        dp[0] = 1;
        Map<Character, Integer> lastIndex = new HashMap<>();

        for (int i = 0; i < n; i++) {
            dp[i + 1] = (dp[i] * 2) % MOD;
            char c = s.charAt(i);
            if (lastIndex.containsKey(c)) {
                dp[i + 1] = (dp[i + 1] - dp[lastIndex.get(c)] + MOD) % MOD;
            }
            lastIndex.put(c, i);
        }

        return (dp[n] - 1 + MOD) % MOD; // Subtract the empty subsequence
    }

    public static void main(String[] args) {
        Solution sol = new Solution();
        System.out.println(sol.distinctSubseqII("abc"));  // Output: 7
    }
}

C++

#include <iostream>
#include <vector>
#include <unordered_map>

using namespace std;

class Solution {
public:
    int distinctSubseqII(string s) {
        int n = s.length();
        const int MOD = 1e9 + 7;
        vector<int> dp(n + 1, 0);
        unordered_map<char, int> lastIndex;
        dp[0] = 1;

        for (int i = 0; i < n; ++i) {
            dp[i + 1] = (dp[i] * 2) % MOD;
            if (lastIndex.find(s[i]) != lastIndex.end()) {
                dp[i + 1] = (dp[i + 1] - dp[lastIndex[s[i]]]) % MOD;
            }
            lastIndex[s[i]] = i;
        }

        return (dp[n] - 1 + MOD) % MOD; // Subtract the empty subsequence
    }
};

int main() {
    Solution sol;
    cout << sol.distinctSubseqII("abc") << endl;  // Output: 7
    return 0;
}

JavaScript

function distinctSubseqII(s) {
    const MOD = 1e9 + 7;
    const dp = new Array(s.length + 1).fill(0);
    dp[0] = 1;
    const lastIndex = {};

    for (let i = 0; i < s.length; i++) {
        dp[i + 1] = (dp[i] * 2) % MOD;
        if (s[i] in lastIndex) {
            dp[i + 1] = (dp[i + 1] - dp[lastIndex[s[i]]] + MOD) % MOD;
        }
        lastIndex[s[i]] = i;
    }

    return (dp[s.length] - 1 + MOD) % MOD; // Subtract the empty subsequence
}

console.log(distinctSubseqII("abc")); // Output: 7

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define MOD 1000000007

int distinctSubseqII(char *s) {
    int n = strlen(s);
    long *dp = (long *)calloc(n + 1, sizeof(long));
    int *lastIndex = (int *)calloc(26, sizeof(int));
    memset(lastIndex, -1, 26 * sizeof(int));
    
    dp[0] = 1; // Represents the empty subsequence

    for (int i = 0; i < n; ++i) {
        dp[i + 1] = (dp[i] * 2) % MOD;
        if (lastIndex[s[i] - 'a'] != -1) {
            dp[i + 1] = (dp[i + 1] - dp[lastIndex[s[i] - 'a']]) % MOD;
            if (dp[i + 1] < 0) dp[i + 1] += MOD;
        }
        lastIndex[s[i] - 'a'] = i;
    }
    
    long result = (dp[n] - 1 + MOD) % MOD; // Subtract empty subsequence
    
    free(dp);
    free(lastIndex);
    return (int)result;
}

int main() {
    char s[] = "abc";
    printf("%d\n", distinctSubseqII(s));  // Output: 7
    return 0;
}

using System;
using System.Collections.Generic;

public class Solution {
    public int DistinctSubseqII(string s) {
        int MOD = 1000000007;
        int n = s.Length;
        int[] dp = new int[n + 1];
        dp[0] = 1;
        Dictionary<char, int> lastIndex = new Dictionary<char, int>();

        for (int i = 0; i < n; i++) {
            dp[i + 1] = (dp[i] * 2) % MOD;
            if (lastIndex.ContainsKey(s[i])) {
                dp[i + 1] = (dp[i + 1] - dp[lastIndex[s[i]]] + MOD) % MOD;
            }
            lastIndex[s[i]] = i;
        }

        return (dp[n] - 1 + MOD) % MOD; // Subtract the empty subsequence
    }

    public static void Main(string[] args) {
        Solution sol = new Solution();
        Console.WriteLine(sol.DistinctSubseqII("abc"));  // Output: 7
    }
}

The Python solution utilizes a list for dynamic programming and a dictionary to track the last seen location of each character in the string. This aids in removing duplicate subsequences contributions.

Complexity

Time Complexity: O(n), where n is the length of the string s.

Space Complexity: O(n + 26), for the dp array and the last seen dictionary.

Try this approach in the editor

Approach 2: Space Optimized Dynamic Programming

This approach optimizes the space used by reducing the need for a full array for dynamic programming calculations, utilizing only necessary data to minimize space consumption.

Python

def distinctSubseqII(s: str) -> int:
    MOD = 10**9 + 7
    lastIndex = {}
    curr = 1

    for char in s:
        prev = curr
        curr = (curr * 2) % MOD
        if char in lastIndex:
            curr = (curr - lastIndex[char]) % MOD
        lastIndex[char] = prev

    return (curr - 1) % MOD  # Subtracting the empty subsequence

print(distinctSubseqII("abc"))  # Output: 7

JavaScript

function distinctSubseqII(s) {
    const MOD = 1e9 + 7;
    const lastIndex = {};
    let curr = 1;

    for (let char of s) {
        const prev = curr;
        curr = (curr * 2) % MOD;
        if (char in lastIndex) {
            curr = (curr - lastIndex[char] + MOD) % MOD;
        }
        lastIndex[char] = prev;
    }

    return (curr - 1 + MOD) % MOD; // Subtract the empty subsequence
}

console.log(distinctSubseqII("abc")); // Output: 7

This Python solution does not use a dp array but instead keeps track of subsequences using only two variables, processing each character efficiently and reducing the space complexity significantly.

Complexity

Time Complexity: O(n), for processing each character in the string.

Space Complexity: O(26), reduced by maintaining states for each character explicitly without a full dp array.

Try this approach in the editor

Approach 3: Default Approach

TypeScript

function distinctSubseqII(s: string): number {
    const mod = 1e9 + 7;
    const dp = new Array(26).fill(0);
    for (const c of s) {
        dp[c.charCodeAt(0) - 'a'.charCodeAt(0)] = dp.reduce((r, v) => (r + v) % mod, 0) + 1;
    }
    return dp.reduce((r, v) => (r + v) % mod, 0);
}

func distinctSubseqII(s string) int {
	const mod int = 1e9 + 7
	sum := func(arr []int) int {
		x := 0
		for _, v := range arr {
			x = (x + v) % mod
		}
		return x
	}

	dp := make([]int, 26)
	for _, c := range s {
		c -= 'a'
		dp[c] = sum(dp) + 1
	}
	return sum(dp)
}

Rust

impl Solution {
    pub fn distinct_subseq_ii(s: String) -> i32 {
        const MOD: i32 = (1e9 as i32) + 7;
        let mut dp = [0; 26];
        for u in s.as_bytes() {
            let i = (u - &b'a') as usize;
            dp[i] = ({
                let mut sum = 0;
                dp.iter().for_each(|&v| {
                    sum = (sum + v) % MOD;
                });
                sum
            }) + 1;
        }
        let mut res = 0;
        dp.iter().for_each(|&v| {
            res = (res + v) % MOD;
        });
        res
    }
}

Try this approach in the editor

Complexity comparison

Approach	Complexity
Dynamic Programming with Last Seen	Time Complexity: O(n), where n is the length of the string s. Space Complexity: O(n + 26), for the dp array and the last seen dictionary.
Space Optimized Dynamic Programming	Time Complexity: O(n), for processing each character in the string. Space Complexity: O(26), reduced by maintaining states for each character explicitly without a full dp array.
Default Approach	–

Approach

Complexity

Dynamic Programming with Last Seen

Time Complexity: O(n), where n is the length of the string s.

Space Complexity: O(n + 26), for the dp array and the last seen dictionary.

Space Optimized Dynamic Programming

Time Complexity: O(n), for processing each character in the string.

Space Complexity: O(26), reduced by maintaining states for each character explicitly without a full dp array.

Default Approach

–

Complexity analysis

Approach	Time	Space	When to Use
Dynamic Programming with Last Seen	O(n)	O(n)	General solution that clearly shows how duplicates are removed using last occurrence tracking
Space Optimized Dynamic Programming	O(n)	O(1)	When memory matters or when the alphabet size is small and fixed

Frequently asked questions

Is Distinct Subsequences II easy or hard?

Distinct Subsequences II is classified as a Hard problem because it requires careful dynamic programming state design and handling of duplicate subsequences. Many candidates initially overcount results until they recognize the need to subtract contributions from previous occurrences.

Distinct Subsequences II Python/Java solution

Python and Java implementations follow the same dynamic programming formula: dp[i] = 2 * dp[i-1] minus the count before the last occurrence of the current character. Both languages usually store last positions in an array or dictionary and apply modulo 1e9+7 to avoid overflow.

How to solve Distinct Subsequences II in O(n)?

Use dynamic programming where dp[i] represents the number of distinct subsequences using the first i characters. For each new character, double the previous count and subtract the contribution from its previous occurrence to remove duplicates. Tracking last positions with an array or hash map ensures the algorithm processes the string in linear time.

What is the best approach for Distinct Subsequences II?

The best approach uses dynamic programming with a last-seen index for each character. Each step doubles the number of subsequences and subtracts duplicates created by earlier occurrences of the same character. This method runs in O(n) time and handles repeated characters correctly using a hash map or fixed array.

Is Distinct Subsequences II asked at Google/Amazon/Meta?

Distinct subsequence counting problems appear frequently in interviews at companies like Google, Amazon, and Meta because they test dynamic programming reasoning and duplicate handling. Variations of this problem are commonly used to evaluate DP state design and optimization skills.

What data structure is used in Distinct Subsequences II?

The solution primarily uses dynamic programming along with an auxiliary structure to track the last occurrence of each character. This is typically implemented using a hash map or a fixed array of size 26 for lowercase letters. These structures help subtract duplicate subsequences efficiently.

What is the time complexity of Distinct Subsequences II?

The optimal solution runs in O(n) time where n is the length of the string. Each character is processed once while updating the dynamic programming state and checking the previous occurrence of the character. Space complexity is O(n) for the DP array or O(1) with the space‑optimized version.

Distinct Subsequences II solution and explanation

The problem

Approach overview

Approach 1: Dynamic Programming with Last Seen

Approach 2: Space Optimized Dynamic Programming

Approach 3: Default Approach

Complexity comparison

Complexity analysis

Frequently asked questions

Comments

Distinct Subsequences II solution and explanation

The problem

Approach overview

Approach 1: Dynamic Programming with Last Seen

Approach 2: Space Optimized Dynamic Programming

Approach 3: Default Approach

Complexity comparison

Complexity analysis

Frequently asked questions

Comments

Related problems