#115

Hard

auto_awesomeState transition dynamic programming

LeetCode Problem Workspace

Distinct Subsequences

Compute the number of distinct subsequences of one string matching another using precise state transition dynamic programming.

string dynamic programming

Problem Statement

Given two strings s and t, calculate the total number of distinct subsequences in s that match t exactly. Each subsequence must maintain the original order of characters from s but can skip any number of characters.

You must return an integer representing the count of these distinct subsequences. The inputs are guaranteed such that the answer fits in a 32-bit signed integer, with s and t consisting only of English letters, and lengths ranging from 1 to 1000.

Examples

Example 1

Input: s = "rabbbit", t = "rabbit"

Output: 3

As shown below, there are 3 ways you can generate "rabbit" from s. rabbbit rabbbit rabbbit

Example 2

Input: s = "babgbag", t = "bag"

Output: 5

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

Constraints

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

Solution Approach

Dynamic Programming Table Setup

Create a 2D dp array where dp[i][j] represents the number of ways the first j characters of t can be formed from the first i characters of s. Initialize dp[0][0] = 1 and dp[i][0] = 1 for all i, since an empty t is always a subsequence.

State Transition Rules

For each character in s, if it matches the current character in t, dp[i][j] = dp[i-1][j-1] + dp[i-1][j]. If it does not match, inherit the previous count: dp[i][j] = dp[i-1][j]. This ensures all valid subsequences are counted without duplication.

Space Optimization

Since dp[i][j] only depends on the previous row, use a single 1D array to reduce space complexity from O(n*m) to O(m). Update the array in reverse order for t indices to preserve previous values during iteration.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

Time complexity is O(n m) for strings of lengths n and m, as each dp cell is computed once. Space complexity is O(m) with optimization, otherwise O(n m). Performance depends on careful DP state updates to avoid overcounting.

What Interviewers Usually Probe

Check if the candidate identifies dp[i][j] meaning and proper initialization.
Watch if they correctly implement the state transition without skipping edge cases.
Notice if they attempt space optimization or remain with full 2D table.

Common Pitfalls or Variants

Common pitfalls

Confusing character positions and misaligning indices in the dp table.
Forgetting to initialize dp[i][0] = 1, which causes incorrect counts for empty target subsequences.
Overwriting previous dp values during optimization, leading to undercounting.

Follow-up variants

Compute subsequences modulo a large prime to prevent integer overflow.
Count distinct subsequences that match t but allow at most k skipped characters in between.
Find the minimum-length subsequence in s that can generate t multiple times.

FAQ

What is the main pattern behind the Distinct Subsequences problem?

It follows state transition dynamic programming where dp[i][j] counts ways to form t[0..j-1] from s[0..i-1].

Can this problem be solved without dynamic programming?

Recursive solutions exist but are inefficient due to overlapping subproblems; DP ensures polynomial time.

How do you handle empty target strings?

An empty target t is a subsequence of any prefix of s, so dp[i][0] = 1 for all i.

Is space optimization important here?

Yes, using a 1D array reduces space from O(n*m) to O(m) while preserving correct counts.

What common mistakes should be avoided?

Misaligned indices, forgetting base cases, and overwriting previous dp values during optimization are frequent errors.

terminal

Solution

Solution 1: Dynamic Programming

We define $f[i][j]$ as the number of schemes where the first $i$ characters of string $s$ form the first $j$ characters of string $t$. Initially, $f[i][0]=1$ for all $i \in [0,m]$.

1

2

3

4

5

6

7

8

9

10

11

12

class Solution:
    def numDistinct(self, s: str, t: str) -> int:
        m, n = len(s), len(t)
        f = [[0] * (n + 1) for _ in range(m + 1)]
        for i in range(m + 1):
            f[i][0] = 1
        for i, a in enumerate(s, 1):
            for j, b in enumerate(t, 1):
                f[i][j] = f[i - 1][j]
                if a == b:
                    f[i][j] += f[i - 1][j - 1]
        return f[m][n]

Solution 2

#### Python3

1

2

3

4

5

6

7

8

9

10

11

12

class Solution:
    def numDistinct(self, s: str, t: str) -> int:
        m, n = len(s), len(t)
        f = [[0] * (n + 1) for _ in range(m + 1)]
        for i in range(m + 1):
            f[i][0] = 1
        for i, a in enumerate(s, 1):
            for j, b in enumerate(t, 1):
                f[i][j] = f[i - 1][j]
                if a == b:
                    f[i][j] += f[i - 1][j - 1]
        return f[m][n]

Continue Practicing

#131 palindrome partitioning #132 palindrome partitioning ii #97 interleaving string