Leetcode Problem 940. Distinct Subsequences II

940. Distinct Subsequences II

Leetcode Solutions

Initialize a dp array of length n + 1, where n is the length of the string s. Set dp[0] to 1, representing the empty subsequence.
Create a dictionary last to keep track of the last index where each character was seen.
Iterate over the characters of the string using index i from 1 to n.
For each character s[i-1], update dp[i] to 2 * dp[i-1].
If s[i-1] was seen before (let's say at index j), subtract dp[j] from dp[i] to avoid double counting.
Update the last dictionary with the current index for s[i-1].
Since we are interested in non-empty subsequences, subtract 1 from the final result.
Return dp[n] modulo 10^9 + 7.

Programming Language

Purpose:

General Question

Debug My Code

image/screenshot of info(optional)

Full Screen