Skip to main content

115. Distinct Subsequences

hard

Count the number of distinct subsequences of s that equal t. The classic recursion-into-DP transformation problem — branching on 'match or skip' translates straight into a 2D table.

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: There are 3 ways you can generate "rabbit" from "rabbbit" by deleting one of the three 'b' characters.

Example 2

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

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

Recurse on (i, j) — i is the index into s, j is the index into t. count(i, j) = number of ways s[i..] matches t[j..].

Hint 2

Base: j == t.length -> 1 (already matched fully). i == s.length and j < t.length -> 0.

Hint 3

Recursive: if s[i] == t[j], count(i, j) = count(i+1, j+1) (use s[i]) + count(i+1, j) (skip s[i]). Else count(i, j) = count(i+1, j).

Hint 4

Memoize on (i, j). Or build a 2D DP table filled right-to-left.

Solution approach

Reveal approach

Recursive count(i, j) returns the number of distinct ways s[i..] can produce t[j..]. Base cases: j == t.length -> return 1 (one valid way: skip everything left in s); i == s.length -> return 0 (can't match more of t). Recursive: if s[i] == t[j], result = count(i+1, j+1) + count(i+1, j) (we either consume both chars or skip s[i] hoping for a later match); else result = count(i+1, j). Memoize on (i, j). Iterative DP: dp[i][j] = count of ways for suffixes. Fill from bottom-right to top-left. Final answer is dp[0][0]. Time and space O(m * n) for the 2D table; can be optimized to O(n) using a 1D rolling array.

Complexity

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

Related patterns

  • recursion
  • memoization
  • dynamic-programming

Related problems

Asked at

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

  • Google
  • Amazon
  • Bloomberg

Practice these live with InterviewChamp.AI

Drill Distinct Subsequences and Recursion problems under real interview conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →