Skip to main content

115. Distinct Subsequences

hard

Count how many distinct subsequences of s equal the string t. The two-string DP recurrence: a match lets you take it or skip it; a mismatch forces you to skip s.

By Alex Chen, Founder, InterviewChamp.AI · Last verified

Problem

Given two strings s and t, return the number of distinct subsequences of s which equals t. The test cases are generated so that the answer fits on a 32-bit signed integer.

Constraints

  • 1 <= s.length, t.length <= 1000
  • s and t consist of English letters.

Examples

Example 1

Input
s = "rabbbit", t = "rabbit"
Output
3

Explanation: As shown below, there are 3 ways you can generate "rabbit" from s. rabbbit, rabbbit, rabbbit (each by deleting a different 'b').

Example 2

Input
s = "babgbag", t = "bag"
Output
5

Explanation: As shown below, there are 5 ways you can generate "bag" from s. babgbag, babgbag, babgbag, babgbag, babgbag.

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

dp[i][j] = number of distinct subsequences of s[0..i-1] equal to t[0..j-1].

Hint 2

If s[i-1] == t[j-1], you may either match (use dp[i-1][j-1]) or skip s[i-1] (use dp[i-1][j]). Sum both.

Hint 3

If s[i-1] != t[j-1], you must skip s[i-1]: dp[i][j] = dp[i-1][j].

Hint 4

Base case: dp[i][0] = 1 for every i (empty t matches via one way — the empty subsequence). dp[0][j>0] = 0.

Solution approach

Reveal approach

Bottom-up DP over a 2D table dp[m+1][n+1], where m = len(s) and n = len(t). dp[i][j] is the number of ways s[0..i-1] contains t[0..j-1] as a subsequence. Initialize dp[i][0] = 1 (an empty t is matched exactly once by ignoring all of s) and dp[0][j] = 0 for j > 0. Recurrence: if s[i-1] == t[j-1], dp[i][j] = dp[i-1][j-1] + dp[i-1][j] (take the match, or skip s[i-1]); else dp[i][j] = dp[i-1][j] (must skip s[i-1]). Return dp[m][n]. Space optimization: only the previous row is needed — collapse to O(n) by iterating j from right to left to avoid overwriting dp[j-1] before use.

Complexity

Time
O(m * n)
Space
O(n)

Related patterns

  • dynamic-programming
  • string-dp
  • two-strings-table

Related problems

Asked at

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

  • Bloomberg
  • Google

Practice these live with InterviewChamp.AI

Drill Distinct Subsequences 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 →