# Distinct Subsequences

This page explains Java solution to problem `Distinct Subsequences` using `Dynamic Programming` algorithm.

## Problem Statement

Given a string `S` and a string `T`, count the number of distinct subsequences of `S` which equals `T`.

A subsequence of a string is a new string which is formed from the original string by deleting some (can be none) of the characters without disturbing the relative positions of the remaining characters. (ie, `ACE` is a subsequence of `ABCDE` while `AEC` is not).

Example 1:

Input: S = "rabbbit", T = "rabbit"
Output: 3
Explanation: As shown below, there are 3 ways you can generate "rabbit" from S.
(The caret symbol ^ means the chosen letters)
rabbbit
^^^^ ^^
rabbbit
^^ ^^^^
rabbbit
^^^ ^^^

## Solution

If you have any suggestions in below code, please create a pull request by clicking here.
``````
package com.vc.hard;

class DistinctSubsequences {
public int numDistinct(String s, String t) {
/**
0  r  a  b  b  i  t
0 1, 0, 0, 0, 0, 0, 0
r 1, 1, 0, 0, 0, 0, 0
a 1, 1, 1, 0, 0, 0, 0
b 1, 1, 1, 1, 0, 0, 0
b 1, 1, 1, 2, 1, 0, 0
b 1, 1, 1, 3, 3, 0, 0
i 1, 1, 1, 3, 3, 3, 0
t 1, 1, 1, 3, 3, 3, 3
*/
int sn = s.length();
int tn = t.length();
int[][] dp = new int[sn + 1][tn + 1];
for(int i = 0; i <= sn; i++) {
for(int j = 0; j <= tn; j++) {
if(i == 0 && j == 0) dp[i][j] = 1;
else if(i == 0) {
dp[i][j] = 0;
}
else if(j == 0) {
dp[i][j] = 1;
}
else {
dp[i][j] = dp[i - 1][j];
if(s.charAt(i - 1) == t.charAt(j - 1)) dp[i][j] += dp[i - 1][j - 1];
}
}
}
return dp[sn][tn];
}
}

``````

## Time Complexity

O(M * N) Where
M is total number of elements in an input string S
N is total number of elements in an input string T

## Space Complexity

O(M * N) Where
M is total number of elements in an input string S
N is total number of elements in an input string T