# Fast C# solution using DP O(n^2)

• ``````public int NumDistinct(string s, string t) {
// Check the pre-conditions
if (s == null || t == null)
{
return 0;
}

// We can use DP for this problem.
// Given T := t.Length and S := s.Length()
// We create a matrix dp[T, S]
// In each cell [r,c] we store the possible subsequences
// of s starting at r in s starting at c.
var T = t.Length;
var S = s.Length;

// It is pointless to continue if the search string t is empty
// or is bigger than s
if (T == 0 || T > S)
{
return 0;
}

var dp = new int[T, S];

// First initialize the last row
var count = 0;
int r, c;
r = T - 1;
for (c = S - 1; c >= 0; --c)
{
// If the current char in t is equal to the current char in s
// we have a possible combination...
// We update the count and store it into the cell
if (t[r] == s[c])
{
++count;
}

dp[r, c] = count;
}

// Now we update the rest of the matrix
// We update only the lower triangle, the upper one does not make
// sense to be updated since we have more characters left in t than what
// we have in s, so there is no way we can find a subsequence
var maxCol = S - 1;
for (r = T - 2; r >= 0; --r)
{
--maxCol;
count = 0;
for (c = maxCol; c >= 0; --c)
{
// If the current char in t is equal to the current char in s
// we have a possible combination...
// We update the count and store it into the cell
if (t[r] == s[c])
{
// The count is update by the number of combination advancing t and s
count += dp[r + 1, c + 1];
}

dp[r, c] = count;
}
}

return dp[0, 0];
}``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.