← Accolite questions

Count child string occurrences as subsequences in parent string

Filed under Accolite

Free read 3 of 3

Confirm 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

  1. Confirm whether overlapping or distinct subsequence indices are counted (standard definition counts distinct index subsets).

Solution

O(m * n) time, O(m * n) space

Python
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.