Count child string occurrences as subsequences in parent string
Filed under Accolite
Free read 3 of 3Confirm whether overlapping or distinct subsequence indices are counted (standard definition counts distinct index subsets).
The question
Given a parent string S and a child string T, find the number of times T appears as a subsequence in S.
Constraints
- Length of strings S and T are typically within reasonable limits for dynamic programming (e.g., up to 1000).
- Character case matters.
Examples
- Input
- S = "rabbbit", T = "rabbit"
- Output
- 3
- Why
- There are 3 distinct ways to form "rabbit" as a subsequence of "rabbbit".
Approach
Confirm whether overlapping or distinct subsequence indices are counted (standard definition counts distinct index subsets).
Generate all subsequences of S and count how many match T, which is exponentially slow.
Use 2D Dynamic Programming where dp[i][j] represents the number of times T[0..j-1] appears as a subsequence in S[0..i-1]. If S[i-1] == T[j-1], dp[i][j] = dp[i-1][j-1] + dp[i-1][j].
Empty child string T (always 1 way) or empty parent string S.
Solution
O(m * n) time, O(m * n) space
def numDistinct(s: str, t: str) -> int:
m, n = len(s), len(t)
dp = [[0] * (n + 1) for _ in range(m + 1)]
for i in range(m + 1):
dp[i][0] = 1
for i in range(1, m + 1):
for j in range(1, n + 1):
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]
return dp[m][n]
Tips
- What they are testing: Test when T is longer than S, when T equals S, and when T has repeated characters.
- Common mistake: Using standard LCS formulation instead of counting total valid subsequence matches via dynamic programming recurrence.
Related Accolite questions
Collected from public candidate posts and coding forums. Updated Nov 2026.