Skip to main content

940. Distinct Subsequences II

hard

Count the number of distinct non-empty subsequences of s. Linear DP with a 26-slot 'last seen' table — the 2D framing keeps an inclusion-exclusion correction for each repeated letter.

By Sam K., Founder, InterviewChamp.AI · Last verified

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^9 + 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.

Constraints

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

Examples

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", "ba", "aa" and "aba".

Example 3

Input
s = "aaa"
Output
3

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

Solve it now

Free. No sign-up. Python and JavaScript run instantly in your browser.

Output

Press Run or Cmd+Enter to execute

Hints

Progressive — try the first before opening the next.

Hint 1

Let dp[i] = number of distinct non-empty subsequences of s[0..i].

Hint 2

Without repeats: dp[i] = 2 * dp[i-1] + 1 (every prior subsequence extends or doesn't, plus the new singleton).

Hint 3

With repeats: subtract dp[last[s[i]] - 1] + 1 (without the +1) to remove duplicates created when this letter appeared before.

Hint 4

Track last[c] = the previous index where letter c was seen. Apply mod 10^9 + 7 at every step.

Solution approach

Reveal approach

Linear DP with a 26-slot 'last occurrence' tracker. dp[i] is the count of distinct non-empty subsequences in s[0..i-1]. Base dp[0] = 0. For each i: dp[i] = 2 * dp[i-1] + 1 — each prior distinct subsequence can be extended by s[i-1] or kept as-is, plus the new singleton s[i-1]. If s[i-1] has appeared before at position k (1-indexed), subtract dp[k-1] to remove the duplicates that arose when this same character extended every subsequence already counted in dp[k-1]. All arithmetic mod 10^9 + 7. Add a modular constant correction so the result stays non-negative after subtraction. Update last[s[i-1]] = i. Return dp[n]. The 2D framing comes from the (current index, last-occurrence) pairing — listed in dp-2d for the family.

Complexity

Time
O(n)
Space
O(n)

Related patterns

  • dynamic-programming
  • string-dp

Related problems

Asked at

Companies reported asking this problem (sourced from public Glassdoor, Blind, and Levels.fyi interview posts).

  • Google

More 2D Dynamic Programming practice problems

See all 2D Dynamic Programming problems →