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

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

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