Classic example
Input
s = "rabbbit", t = "rabbit"
Output
3
There are three ways to delete one of the three consecutive 'b's to form 'rabbit'.
Full lesson preview
Count distinct subsequences
Compute how many distinct subsequences of a source string equal a target string using dynamic programming. This classic DP counts ways of choosing characters (not necessarily contiguous).
Python practice30 minDynamic ProgrammingAdvancedLast updated March 29, 2026
Problem statement
Given two strings s (source) and t (target), return the number of distinct subsequences of s which equals t. A subsequence of a string is a new string formed from the original string by deleting some (can be zero) of the characters without disturbing the relative positions of the remaining characters. The characters that remain must appear in the same order as they appear in the original string.
You should design a solution that handles moderately large inputs efficiently. Use dynamic programming, leveraging overlapping subproblems: count how many ways prefixes of s can form prefixes of t.
For example, s = "rabbbit" and t = "rabbit". There are 3 distinct ways to form "rabbit" from "rabbbit" by deleting one of the extra 'b's.
Return the count as an integer. Do not print; your function should return the integer value.
Task
Implement an efficient DP solution (O(n*m) time, O(m) space) to count distinct subsequences of s that match t.
Examples
Input format
Two string arguments: s and t. Example call: count_distinct_subsequences("rabbbit", "rabbit")
Output format
An integer representing the number of distinct subsequences of s that equal t.
Constraints
0 <= len(s), len(t) <= 1000. The result may be large but fits in Python's unlimited integers. Aim for O(len(s) * len(t)) time and O(len(t)) extra space.
Samples
Sample 1
Input
s = "abc", t = ""
Output
1
There is exactly one subsequence of any string equal to the empty string: delete all characters.