115. Distinct Subsequences
Asked at Salesforce
Difficulty
Hard
Time
O(n * m)
Space
O(m)
Pattern
String
Companies
1
Problem
You are given two strings, s and t. Count how many distinct subsequences of s are equal to t.
A subsequence is made by deleting some characters from s without changing the order of the rest. Two ways of deleting are counted as different only if the set of kept positions differs. If the same letters appear in several places, each choice of positions is a separate way.
Return the number of ways as an integer. The answer always fits in a 32-bit signed integer. If t is longer than s, the answer is 0.
Pick positions, keep the order
Constraints
- ●
1 <= s.length, t.length <= 1000 - ●
s and t consist of English letters - ●
The answer fits in a 32-bit signed integer
Examples
s = "rabbbit", t = "rabbit"3s = "babgbag", t = "bag"5Asked At
1 companies| Company | Difficulty | |
|---|---|---|
| Salesforce | Hard | View all Salesforce questions → |
How to Think About It
Brute force: generate all 2^n subsequences of s, check each against t. Time is O(2^n * m) which is exponential.
Define dp[i][j] as the number of ways to form t[0..j-1] using s[0..i-1]. Base case: dp[i][0] = 1 for all i (one way to form empty string).
Recurrence: if s[i-1] == t[j-1], then dp[i][j] = dp[i-1][j-1] + dp[i-1][j] (use the character or skip it). Otherwise, dp[i][j] = dp[i-1][j] (must skip).
The answer is dp[n][m] where n = len(s) and m = len(t). If m > n, the answer is 0 immediately.
Space can be optimized to O(m) by using a single row and updating it right-to-left to avoid overwriting values needed for the next computation.
Example: s = "rabbbit", t = "rabbit". dp[7][6] = 3. The three ways are: ra_b_b_it, ra_bb_bit, rab_bb_it (underscores mark removed b's).
Optimal Approach
Step 1: If len(t) > len(s), return 0 immediately.
Step 2: Create a 2D dp table of size (n+1) x (m+1) where n = len(s), m = len(t). Initialize dp[i][0] = 1 for all i from 0 to n.
Step 3: Fill the table row by row. For each i from 1 to n and j from 1 to m:
- If
s[i-1] == t[j-1]:dp[i][j] = dp[i-1][j-1] + dp[i-1][j] - Else:
dp[i][j] = dp[i-1][j]
Step 4: Return dp[n][m].
Step 5: Space-optimized: use a 1D array dp of size m+1. dp[0] = 1, rest 0. For each character in s, iterate j from m down to 1: if s[i] == t[j-1], then dp[j] += dp[j-1].
Step 6: Example walkthrough with s = "babgbag", t = "bag":
After processing s: dp = [1, 0, 0, 0]
s[0]=b: dp = [1, 1, 0, 0]
s[1]=a: dp = [1, 1, 1, 0]
s[2]=b: dp = [1, 2, 1, 0]
s[3]=g: dp = [1, 2, 1, 1]
s[4]=b: dp = [1, 3, 1, 1]
s[5]=a: dp = [1, 3, 4, 1]
s[6]=g: dp = [1, 3, 4, 5]
Answer is 5.
Time: O(n * m). Space: O(m) with optimization, O(n * m) for the full table.
1D DP, updated right to left
What Trips People Up in Real Interviews
Confusing this with the longest common subsequence problem. LCS asks for length, this asks for count of ways.
Forgetting the base case dp[i][0] = 1. Without it, you miss the count for empty t.
Going left-to-right in the space-optimized version, which overwrites dp[j-1] before it is used. Go right-to-left.
Not pruning the early return when m > n. It is a simple check that saves time and shows edge-case awareness.
Mixing up the indices: dp[i][j] uses s[i-1] and t[j-1] because strings are 0-indexed but dp is 1-indexed.
Solution Code
O(n * m) timeclass Solution:
def numDistinct(self, s: str, t: str) -> int:
n, m = len(s), len(t)
if m > n:
return 0
dp = [0] * (m + 1)
dp[0] = 1
for i in range(n):
for j in range(m - 1, -1, -1):
if s[i] == t[j]:
dp[j + 1] += dp[j]
return dp[m]Frequently Asked Questions
What is the Distinct Subsequences problem?
Given two strings s and t, count the number of distinct subsequences of s that equal t. A subsequence is formed by deleting some characters without changing the order.
How do you solve Distinct Subsequences?
The optimal approach runs in O(n * m) time and O(m) space. Scroll up to "Optimal Approach" for the step-by-step walkthrough, diagrams, and code in Python, C++ and Java.
What companies ask Distinct Subsequences?
Distinct Subsequences is asked at Salesforce. It is a hard difficulty problem.
What are common mistakes on Distinct Subsequences?
- Confusing this with the longest common subsequence problem. LCS asks for length, this asks for count of ways.
- Forgetting the base case `dp[i][0] = 1`. Without it, you miss the count for empty t.
- Going left-to-right in the space-optimized version, which overwrites `dp[j-1]` before it is used. Go right-to-left.
- Not pruning the early return when `m > n`. It is a simple check that saves time and shows edge-case awareness.
- Mixing up the indices: `dp[i][j]` uses `s[i-1]` and `t[j-1]` because strings are 0-indexed but dp is 1-indexed.