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 Alex Chen, 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

Practice these live with InterviewChamp.AI

Drill Distinct Subsequences II and 2D Dynamic Programming problems under real interview conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →