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 Sam K., 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

More 2D Dynamic Programming practice problems

See all 2D Dynamic Programming problems →