logo
logo

Distinct Subsequences

Lesson
Given a string 
s
 and a string 
t
, write a function to count the number of distinct subsequences of 
t
 in 
s
. A subsequent of a string is a new string that can be formed from the original string by deleting some of the characters, but you cannot change the position of any characters. For example, if 
s
 is "rabbit" and 
t
 is "rbt", then the output should be 3 because you can create three different subsequences out of "rabbit" by deleting the characters in "rbt" (i.e. "ra_it", "rab_t", and "ra__it").Write a function that takes in two string parameters 
s
 and 
t
, and returns an integer representing the number of distinct subsequences of 
t
 in 
s
.

Example:

calculateDistinctSubsequences("rabbit", "rbt") => 3

Walkthrough

To solve this problem, we can use a dynamic programming approach.

function calculateDistinctSubsequences(s, t) {
  let dp = new Array(t.length + 1).fill().map(() => new Array(s.length + 1));

  for (let i = 0; i <= s.length; i++) {
    dp[0][i] = 1;
  }

  for (let i = 1; i <= t.length; i++) {
    dp[i][0] = 0;
    for (let j = 1; j <= s.length; j++) {
      if (t.charAt(i-1) === s.charAt(j-1)) {
        dp[i][j] = dp[i-1][j-1] + dp[i][j-1];
      } else {
        dp[i][j] = dp[i][j-1];
      }
    }
  }

  return dp[t.length][s.length];
}
We create a temporary 2D array where the rows will represent the characters in 
t
 and the columns will represent the characters in 
s
. We initialize the first row to all 1's, and the first column to all 0's except for the first element which will be 1. This is because an empty string is always a subsequence of any string, and we can only create a subsequence of 
t
 from 
s
 if the characters in 
t
 match the characters in 
s
.Next, we loop through the remaining elements of the temporary array and fill it according to the following conditions: If the character in 
t
 matches the character in 
s
, then we can either include or exclude the character in 
s
 to form a subsequence of 
t
. The number of distinct subsequences will be the sum of the number of subsequences that include the character in 
s
 and the number of subsequences that exclude the character in 
s
. If the characters do not match, then we cannot include the character in 
s
, and the number of distinct subsequences will be the same as the number of subsequences formed by excluding the character in 
s
.Finally, we return the value in the last element of the temporary array, which represents the number of distinct subsequences of 
t
 in 
s
.

Big O Complexity Analysis:

The time complexity of this solution is O(mn), where m is the length of 
t
 and n is the length of 
s
. This is because we are filling a 2D array with m rows and n columns. The space complexity is also O(mn), since we are using a temporary 2D array to store the number of distinct subsequences.
Previous LessonNext Lesson