# DP Problem (Count distinct occurrences as a subsequence)

1 min readJan 5, 2020

Given a two strings S and T, find count of distinct occurrences of T in S as a subsequence.

# Python3 program to count number of times

# S appears as a subsequence in T

def findSubsequenceCount(S, T):m = len(T)

n = len(S)# T can't appear as a subsequence in S

if m > n:

return 0# mat[i][j] stores the count of

# occurrences of T(1..i) in S(1..j).

mat = [[0 for _ in range(n + 1)]

for __ in range(m + 1)]# Initializing first column with all 0s. x

# An empty string can't have another

# string as suhsequence

for i in range(1, m + 1):

mat[i][0] = 0# Initializing first row with all 1s.

# An empty string is subsequence of all.

for j in range(n + 1):

mat[0][j] = 1# Fill mat[][] in bottom up manner

for i in range(1, m + 1):

for j in range(1, n + 1):# If last characters don't match,

# then value is same as the value

# without last character in S.

if T[i - 1] != S[j - 1]:

mat[i][j] = mat[i][j - 1]

# Else value is obtained considering two cases.

# a) All substrings without last character in S

# b) All substrings without last characters in

# both.

else:

mat[i][j] = (mat[i][j - 1] +

mat[i - 1][j - 1])return mat[m][n]