Distinct Subsequences
Asked at Salesforce
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.
Asked At
| 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.
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
class 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 is described in detail above, including step-by-step walkthroughs, complexity analysis, and solution code in Python. Scroll up to the "Optimal Approach" section.
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.