Count number of distinct subsequences in Javascript

Hello programmers, In this article we are going to solve a very interesting dynamic programming problem which is also asked in
many JavaScript coding interviews. The problem statement is given below –

You are given two strings str1 and str2. You have to find the number of distinct subsequences in str1 with is equal to str2. For example,
let’s say str1 = “abbc” and str2 = “abc”. Here subsequence [0,1,3] and [0,2,3] are subsequences in str1 which equals str2. Here number denotes indices (0-based).

Understanding the problem paradigm.

As we are given two strings, one brute force approach which comes into mind is we will generate all the subsequence of str1 and match them with str2. If they are the same we will increment the counter variable which we will declare before generating the subsequences. Now when generating all subsequence comes to the mind recursion should be an obvious approach that can be used.

But following this approach, we will take exponential time in generating all subsequences and extra O(str2.length) time to compare the subsequences. We can think of it in a bit different way using recursion. We can compare these two strings recursively and after thinking for a few minutes coming to a recurrence relation will not be that hard. Now after some observation, we can see there are overlapping subproblems in the recursive code so we can use dynamic programming to further reduce time complexity.

Understanding the recurrence relation.

Here we will denote each string with an index. When I say index 2 of str1, this means substring of str1 starting from index 2 till the end of the string.

We will use two variable to denote string which is being processed. There will be 2 states of this recursive solution each being indices on the two strings. The recurrence relation will be following –

dp[i][j] = dp[i+1][j] (if str1[i] !== str2[j])
dp[i][j] = dp[i+1][j] + dp[i+1][j+1]  if(str1[i] === str2[j])

Understanding base cases.

One base case will be if str2 is empty then there always will be 1 subsequence in str1 which will be an empty subsequence which will be equal to str2. Second base case will be if str1 is empty and str2 is not empty then there will be no subsequence which will match str2. So the base cases are –

dp[i][j] = 1 (if j == 0)
dp[i][j] = 0 (if i == 0)

Writing the JavaScript code! Count number of distinct subsequences

Following is a Javascript implementation of the approach discussed above –

// Here we have to count occurence of "abbc" in "abc"
let str1 = "abbc";
let str2 = "abc";

//Finding length of both strings
let n = str1.length;
let m = str2.length;

//Initialising 2d dp array
let dp = new Array(n + 1);
for (let i = 0; i <= n; i++) {
    dp[i] = new Array(m + 1);
}

//Iterating and filling 2d dp array
for (let i = n; i >= 0; i--) {
    for (let j = m; j >= 0; j--) {
        //intialising every element of the 2d array with 0.
        dp[i][j] = 0;

        //Base Case 1
        if (j == m) {
            dp[i][j] = 1;
            //Base Case 2
        } else if (i == n) {
            dp[i][j] = 0;
        } else {
            //writing recurrence
            if (str1[i] === str2[j]) {
                dp[i][j] += dp[i + 1][j + 1] + dp[i + 1][j];
            } else {
                dp[i][j] += dp[i + 1][j];
            }
        }
    }
}

//output the answer.
console.log(dp[0][0]);

Output : 2

You may also learn,

• Using JavaScript Sort in Different Ways