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 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: 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

More Recursion practice problems

See all Recursion problems →